题目来源：2018集训队互测 Round17 T2
题意：
题解：
显然我是不可能想出来的……但是觉得这题题解太神了就来搬(chao)一下……Orzpyz！
显然不会无解……
为了方便计算石子个数，在最后面加一堆$a_i=c_i=\infty$的石子，确保每次取石子都可以取满$k$个；
先考虑$a_i=0$的情况：
设$f_{i,j}$表示只考虑第0到$i$堆石子，通关前$j$轮的最少操作次数；
设$g_{i,j}$表示只考虑第0到$i$堆石子，前$j$轮结束后再取若干次石子，每次取$k$个，使得第$i$堆前面的所有石堆都被取尽的最少操作次数；
分别记$sa,sb$为$a,b$的前缀和；
从小到大枚举$i,j$，每次考虑加入石堆$i$的影响，分两种情况转移：
若存在一种方案使得不取第$i$堆石子即可通关前$j$轮，此时需满足$j\times b_i\leq c_i$且$f_{i-1,j}\neq\infty$；
则转移为：
$f_{i,j}\leftarrow f_{i-1,j}$
$g_{i,j}\leftarrow \lceil\frac{j\times sb_{i-1}}{k}\rceil$
第二种转移需要满足石子总数够取，即$\lceil\frac{j\times sb_{i-1}}{k}\rceil\times k\leq j\times sb_i$；
否则枚举最后一次取$i$的轮数$r$，此时最优策略一定是分成三部分：
1.在前$r$轮取完$[0,i)$中的石子，这部分答案显然为$g_{i,r}$
2.这轮在$i$中取若干次石子，此时$i$中剩余石子数为$m=r\times sb_i-k\times g_{i,r}$，为了使它在$j$轮后不超过限制，还需要取$x=\lceil\frac{max(0,m+(j-r)\times b_i-c_i)}{k}\rceil$次；若$x\times k>m$，即石子不够取，则无解；
3.在剩余的$j-r$轮中取石子，这部分跟第一种情况类似，可以得到$f$的操作数为$f_{i-1,j-r}$，$g$的操作数为$g_{i,j}$；
因此转移就是：
$f_{i,j}\leftarrow g_{i,r}+f_{i-1,j-r}+x$
$g_{i,j}\leftarrow g_{i,r}+\lceil\frac{(j-r)\times sb_{i-1}}{k}\rceil+x$
时间复杂度$O(nt^2)$；
考虑$a_i\neq 0$的情况，可以发现此时对dp的影响只有第二种情况的第三步中，所有石堆的个数都为0；那么直接在$f,g$后面加一维0/1位表示每堆石子初始时是否有值，在第三步转移中用$f_{i-1,j-r,0}$转移，每次计算剩余石子时注意初始的$a_i$即可；
代码看(chao)了天下第一wxh的代码
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 100000000000000000
#define eps 1e-9
using namespace std;
typedef long long ll;
typedef double db;
int n,t,k;
ll tmp,tt,m,a[],b[],c[],sa[],sb[],f[][][],g[][][];
int main(){
scanf("%d%d%d",&n,&t,&k);
for(int i=;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
sa[i]=sa[i-]+a[i];
sb[i]=sb[i-]+b[i];
}
n++;
a[n]=c[n]=sa[n]=inf;
sb[n]=sb[n-];
for(int i=;i<=n;i++){
for(int j=;j<=t;j++){
for(int t=;t<=;t++){
f[i][j][t]=g[i][j][t]=inf;
//transform 1
if(j*b[i]+t*a[i]<=c[i]&&f[i-][j][t]!=inf){
f[i][j][t]=f[i-][j][t];
tmp=(j*sb[i-]+t*sa[i-]+k-)/k;
if(tmp*k<=j*sb[i]+t*sa[i]){
g[i][j][t]=tmp;
}
}
//transform 2
for(int r=;r<j;r++){
if(g[i][r][t]!=inf){
m=r*sb[i]+t*sa[i]-k*g[i][r][t];
tmp=(max(0ll,m+(j-r)*b[i]-c[i])+k-)/k;
if(tmp*k<=m&&f[i-][j-r][]!=inf){
f[i][j][t]=min(f[i][j][t],f[i-][j-r][]+g[i][r][t]+tmp);
tt=((j-r)*sb[i-]+k-)/k;
if(tt*k<=(j-r)*sb[i]+m-tmp*k){
g[i][j][t]=min(g[i][j][t],g[i][r][t]+tmp+tt);
}
}
}
}
}
}
}
printf("%lld",f[n][t][]);
return ;
}