题目大意

　　有 \(n\) 堆石子，初始时第 \(i\) 堆石子有 \(a_i\) 个。

　　你每次取石子会取 \(k\) 个。在你取完一堆石子之后才能在下一堆中取石子。

　　游戏会进行 \(t\) 轮，每轮会发生以下事件：

• 你可以进行任意次取石子操作。
• 每堆的石子个数会增加，具体的，第 \(i\) 堆的式子个数会增加 \(b_i\) 个。

　　每一堆式子有个上限 \(c_i\)，如果在某个时刻，某堆石子的数量超过上限，就就输了。

　　求在不会输掉游戏的前提下，你最少进行几次取石子操作。

　　\(n,t\leq 200,1\leq k\leq {10}^9,0\leq a_i,b_i\leq c_i\leq {10}^9\)。

题解

　　我们可以在最后加一堆 \(a={10}^9,b={10}^9,c={10}^9\times (t+1)\) 的石子堆，这样每次取石子都一定能取到 \(k\) 个。这可以让我们更方便地计算石子个数。

　　先考虑 \(a_i=0\) 的情况。

　　记 \(sa,sb\) 为 \(a,b\) 的前缀和。

　　记 \(f_{i,j}\) 为前 \(i\) 堆石子，进行了 \(j\) 轮游戏，且每次取石子都取了 \(k\) 个的最小操作次数。

　　记 \(g_{i,j}\) 为前 \(i\) 堆石子，进行了 \(j\) 轮游戏，再取了若干次石子，每次石子都取了 \(k\) 个，且 \([1,i)\) 的石堆中没有石子的最小操作次数。

• 如果不取第 \(i\) 种石子也满足要求（即 \(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\) 的时间 \(l\)，我们的策略是：

  • 先在前 \(l\) 轮取完 \([0,i)\)，再取若干次石子：\(g_{i,l}\)
  • 计算要取多少次第 \(i\) 堆的石子：剩余的石子个数是 \(m=l\times sb_{i}-k\times g_{i,l}\)。为了让第 \(i\) 堆的石子不超过上限，我们还要取 \(x=\lceil\frac{\max(0,m+(j-l)\times b_i-c_i)}{k}\rceil\) 次。如果石子不够（\(x\times k>m\)），则无解。
  • 再决策剩下 \(j-l\) 轮。这部分的贡献和第一种情况类似。

  因此，转移为：

  • \(f_{i,j}\leftarrow g_{i,l}+x+f_{i-1,j-l}\)
  • \(g_{i,j}\leftarrow g_{i,l}+x+\lceil\frac{(j-l)\times sb_{i-1}}{k}\rceil\)

　　时间复杂度为 \(O(nt^2)\)。

　　\(a_i\neq 0\) 的情况和 \(a_i=0\) 的情况类似，只需要在某些计算石子个数的地方加上 \(a_i\) 即可。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             //using namespace std;using std::min;using std::max;using std::swap;using std::sort;using std::reverse;using std::random_shuffle;using std::lower_bound;using std::upper_bound;using std::unique;using std::vector;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef long double ldb;typedef std::pair
             
               pii;typedef std::pair
              
                pll;void open(const char *s){#ifndef ONLINE_JUDGE char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}void open2(const char *s){#ifdef DEBUG char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}int upmin(int &a,int b){if(b
               
                a){a=b;return 1;}return 0;}void upmin(ll &a,ll b){ a=min(a,b);}const int N=210;const ll inf=0x3fffffffffffffffll;ll f[N][N][2];ll g[N][N][2];ll a[N],b[N],c[N],sa[N],sb[N];ll ceil(ll a,ll b){ return (a+b-1)/b;}int n,t;ll k;int main(){ open("c"); scanf("%d%d%lld",&n,&t,&k); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&a[i],&b[i],&c[i]); sa[i]=sa[i-1]+a[i]; sb[i]=sb[i-1]+b[i]; }// printf("%lld\n",sa[n]); n++; a[n]=1000000000ll; b[n]=1000000000ll; c[n]=1000000000ll*(t+1); sa[n]=sa[n-1]+a[n]; sb[n]=sb[n-1]+b[n]; for(int i=1;i<=n;i++) for(int j=1;j<=t;j++) { f[i][j][0]=g[i][j][0]=inf; if(0*a[i]+j*b[i]<=c[i]&&f[i-1][j][0]!=inf) { upmin(f[i][j][0],f[i-1][j][0]); if(ceil(j*sb[i-1]+0*sa[i-1],k)*k<=0*sa[i]+j*sb[i]) upmin(g[i][j][0],ceil(j*sb[i-1]+0*sa[i-1],k)); } for(int l=1;l
                
                 m) continue; upmin(f[i][j][0],g[i][l][0]+x+f[i-1][j-l][0]); if(ceil((j-l)*sb[i-1],k)*k<=m-x*k+(j-l)*sb[i]) upmin(g[i][j][0],g[i][l][0]+x+ceil((j-l)*sb[i-1],k)); } } for(int i=1;i<=n;i++) for(int j=0;j<=t;j++) { f[i][j][1]=g[i][j][1]=inf; if(1*a[i]+j*b[i]<=c[i]&&f[i-1][j][1]!=inf) { upmin(f[i][j][1],f[i-1][j][1]); if(ceil(j*sb[i-1]+1*sa[i-1],k)*k<=1*sa[i]+j*sb[i]) upmin(g[i][j][1],ceil(j*sb[i-1]+1*sa[i-1],k)); } for(int l=0;l
                 
                  m) continue; upmin(f[i][j][1],g[i][l][1]+x+f[i-1][j-l][0]); if(ceil((j-l)*sb[i-1],k)*k<=m-x*k+(j-l)*sb[i]) upmin(g[i][j][1],g[i][l][1]+x+ceil((j-l)*sb[i-1],k)); } } ll ans=f[n][t][1]; printf("%lld\n",ans); return 0;}