出题人题解 | #666RPG#

原题解链接：https://ac.nowcoder.com/discuss/157310

简单的计数$dpdp$。

$dp[i][j]dp[i][j]$代表第$ii$个回合后分数为j的方案数

则:$dp[i][j]=dp[i-1][j-ai]dp[i-1][-j]dp[i][j]=dp[i-1][j-ai]\; dp[i-1][-j]$

因为开二维内存不够，需要使用滚动数组

特判屏蔽所有来自$j=666j=666$的状态转移

复杂度$O(n\ast n\ast 1333)O(n*n*1333)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int mod = 1e8+7;
const int maxn=301;
const int ub = 666*301;
const int maxm=666*maxn*2;
int dp[2][maxm*2];
int a[maxn];
int now=1,pre;
int md(int x){return x>=mod?x-mod:x;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    dp[0][0+ub]=1;
    for(int i=1;i<=n;i++){
        for(int j=-ub;j<=ub;j++){
            if(j==666){dp[now][j+ub]=0;continue;}
            dp[now][j+ub]=md(dp[pre][-j+ub] + dp[pre][j-a[i]+ub]);
        }
        now^=1;pre^=1;
    }
    cout<<dp[pre][-666+ub];
    return 0;
}