题目链接：https://ac.nowcoder.com/acm/contest/373/B
题意：有n个回合，每个回合给1个数，每个回合你有两种选择
1.加上第i个数
2.将当前数乘-1
想知道有多少种不同的方案使得 N个回合后分数变为 -666且在任何一个回合之后分数都不为 666。
答案模1e8+7
分析：我们可以用dp[i][j]表示前i个数中当前数为j的方案数有多少
则可以得状态转移方程为dp[i][j]=dp[i-1][j-a[i]]+dp[i-1][-j]
第一维滚动显而易见，但第二维出现了负数，而数组的参数不能为负数，我们则需要设一个变量add,比add大即为整数，否则为负数
注意：add的大小一定要比数组第二维可能最大值要大（这题即需比300*666）大，否则可能出现数组越界情况
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=1<<30; 4 typedef long long ll; 5 const double pi=acos(-1); 6 const int mod=1e8+7; 7 const int maxn=340; 8 const int maxm=610*667; 9 const int add=305*666;//这里要注意 10 ll a[maxn]; 11 ll dp[2][maxm]; 12 int cnt; 13 int main(){ 14 int n;scanf("%d",&n); 15 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 16 dp[0][add]=1; 17 for(int i=1;i<=n;i++){ 18 cnt=i%2; 19 for(int j=-300*666;j<=300*666;j++){ 20 dp[cnt][j+add]=dp[cnt^1][j-a[i]+add]+dp[cnt^1][-j+add]; 21 dp[cnt][j+add]%=mod; 22 } 23 dp[cnt][666+add]=0; 24 } 25 cout<<dp[n%2][-666+add]<<endl; 26 return 0; 27 }
原文：https://www.cnblogs.com/qingjiuling/p/10460630.html