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; }