题解 P7070 【[NWRRC2014]Kebab House】

panyf · 2020-11-13 14:23:08 · 题解

DP。

设 f_{i,j,k,l} 表示做第 i 个烤肉串，用了 j 秒，做了 k 次梦，离可以做梦还有 l 秒的方案数。

转移方程（注意 t=0 的情况）：

时间复杂度 O(nq^2t)，不能通过。

注意到 k\leq\left\lceil\dfrac{q}{t+1}\right\rceil，缩小枚举上界，时间复杂度优化到 O(nq^2)。

前两维可以滚掉，空间复杂度 O(qt)。

为了减少边界特判，代码中的 k 表示做了 k-1 次梦。

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
int f[259][109];
int main(){
    int n,m,t,q,x,i,j,k,l;
    scanf("%d%d",&n,&t),f[1][0]=1;
    for(i=1;i<=n;++i){
        scanf("%d%d",&q,&x),m=min(q-x+1,q/(t+1)+2);
        for(j=1;j<=q;++j){
            for(k=m;k;--k){
                if(t)f[k][0]=(f[k][1]+f[k][0])%P;
                else f[k][0]=(f[k][0]+f[k-1][0])%P;
                for(l=1;l<t;++l)f[k][l]=f[k][l+1];
                if(t)f[k][t]=f[k-1][0];
            }
        }
        for(k=2;k<=m;++k)for(l=0;l<=t;++l)f[1][l]=(f[1][l]+f[k][l])%P,f[k][l]=0;
    }
    for(x=l=0;l<=t;++l)x=(x+f[1][l])%P;
    printf("%d",x);
    return 0;
}