51nod3173 小朋友吃糖果

1.算法分析(DP)

考虑dp,我们令f[i][j]表示,到了第i个差值为两者j的方案数.
很容易想到n^4的暴力dp.这里贴下代码.

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=N*N*2;
const int mod=1e9 + 7;
int s[M],n,f[N][M],a[N],base=200*200;
int main()
{
    cin>>n;int sum=0;
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]),sum+=a[i];
    f[0][base]=1;sum+=base;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=sum;j++)
        {
            for(int k=-a[i];k<=a[i];k++)
            {
                f[i][j]=(f[i][j]+f[i-1][j-k]*1ll*((a[i]-abs(k))/2+1)%mod+mod)%mod;
            }
        }
    }
    cout<<f[n][base]<<endl;
    return 0;
}

2.优化

考虑f[i][j]和f[i][j-1]的转移,这个方程还是可以优化的.

1-3然后各种奇偶,边界判断.
然后每次预处理前缀就可以O(n^3)完成了.
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=N*N*2;
const int mod=1e9+7;
int s[2][M],n,f[N][M],a[N],base=200*200;
int main()
{
    cin>>n;int sum=0;
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]),sum+=a[i];
    f[0][base]=1;sum+=base;
    for(int i=1;i<=n;i++)
    {
        s[0][0]=f[i-1][0];s[1][0]=0;//0奇数,1偶数.
        for(int j=1;j<=sum;j++)
        {
            s[j&1][j]=s[j&1][j-1];
            s[j&1][j]=(s[j&1][j]+f[i-1][j])%mod;
            s[(j-1)&1][j]=s[(j-1)&1][j-1];
        }
        f[i][0]=f[i-1][0];
        for(int k=-a[i];k<=0;k++)
        {
            f[i][0]=(f[i][0]+f[i-1][0-k]*1ll*((a[i]-abs(k))/2+1)%mod)%mod;
        }//暴力计算f[i][0].
        for(int j=1;j<=sum;j++)
        {
            f[i][j]=(f[i][j-1]+f[i-1][j+a[i]])%mod;
            int cnt=(a[i]+j-1)&1;
            if(a[i]+2>j)
            {
                f[i][j]=(((f[i][j]-(s[cnt][j-1]))%mod)+mod)%mod;
            }
            else
            {
                f[i][j]=(((f[i][j]-(s[cnt][j-1]-s[cnt][j-a[i]-2]))%mod)+mod)%mod;
            }
            f[i][j]=(((f[i][j]+(s[!cnt][j+a[i]-1]-s[!cnt][j-1]))%mod)+mod)%mod;
        }
    }
    cout<<f[n][base]<<endl;
    return 0;
}