牛客练习赛41 666RPG（DP好题）

666RPG

题解：

　　这个题和ZOJ - 2972 很像，同样是DP每一轮可能取到的值，不同在于由于数组不能为负数，我们需要重新选一个较大的值作为0基准线，因为无法将二维数组开的太大，所以我们可以定义flag代表第几轮，flag^=1表示当前轮和上一轮来回交替，即dp第一维只用开到2即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn=5e5+10;
const ll mod = 1e8+7;
ll dp[2][maxn];
ll a[310];
int n;
ll zero=2e5;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int flag=0;
    dp[flag][zero]=1;
    for(int i=1;i<=n;i++)
    {
        flag^=1;
        memset(dp[flag],0,sizeof(dp[flag]));
        for(int j=-666*(i-1);j<=666*(i-1);j++)
        {
            if(-j!=666)
            {
                dp[flag][-j+zero]=(dp[flag][-j+zero]+dp[flag^1][j+zero])%mod;
            }
            if(j+a[i]!=666)
            {
                dp[flag][j+a[i]+zero]=(dp[flag][j+a[i]+zero]+dp[flag^1][j+zero])%mod;
            }
        }
    }
    printf("%lld
",dp[n%2][-666+zero]);
}

%杰哥 tql