题解 P6078 【[CEOI2004]糖果】

· · 题解

04年原题，时限 0.1s，内存限制 64MB……

但是时代变了！现在的计算机可以跑得更快了！其实是限制扩大了

然后一种比较暴力的做法就能卡过了

1. 思路

用 dp_{i,j} 来表示取了前 i 种糖果，获得了 j 颗糖果的方案数，很容易得出递推方程

dp_{i,j}=\sum_{k=\max(0,j-m_i)}^{j} dp_{i-1,k}

复杂度 O(nb^2) 当场去世

考虑优化递推方式，首先发现 dp_i 只跟 dp_{i-1} 有关系所以可以开滚动，如果不开的话会 86MLE 身败名裂

然后是方程本身，发现 dp_{i,j} 只是对 dp_{i-1} 的一段数字的求和！

树状数组依旧去世，虽然我没写但是应该过不了

你可以用前缀和，还有另外一种方法，可以发现每次遍历 j 时 j 只增长 1

再看你要求和的区间，不考虑 \max(0,j-m_i) 时，左端点与右端点都同时向右平移一格

那么方程优化为

dp_{i,j}=dp_{i,j-1}+dp_{i-1,j}-dp_{i-1,j-m_i-1}

复杂度优化成 O(nb) 了

大概要跑 1e8，十多年前肯定是跑不过的，但现在比较小菜一碟

2. 代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=10;
const int MAXA=1e7;
const int MAXM=1e6;
const short MOD=2004;

int n,a,b;
int m[MAXN+5];
short dp[2][MAXA+5];
short ans;

int main()
{
//  freopen("sweet.in","r",stdin);
//  freopen("sweet.out","w",stdout);
    scanf("%d %d %d",&n,&a,&b);
    for(int i=1;i<=n;i++) scanf("%d",&m[i]);
    for(int i=0;i<=min(b,m[1]);i++) dp[1][i]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i&1][0]=1;
        for(int j=1;j<=b;j++)
        {
            if(j<=m[i]) dp[i&1][j]=(dp[i&1][j-1]+dp[1-(i&1)][j])%MOD;
            else dp[i&1][j]=(dp[i&1][j-1]+dp[1-(i&1)][j]-dp[1-(i&1)][j-m[i]-1])%MOD;
        }
    }
    for(int i=a;i<=b;i++) ans=(ans+dp[n&1][i])%MOD;
    /*
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=b;j++) cout<<setw(3)<<dp[i][j];
            cout<<endl;
        }
    */
    cout<<(ans+MOD)%MOD<<endl;
    return 0;
}
/*
10 0 10000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000
1000000

3 1 20
3
5
7
*/