B-牛牛想起飞-题解

很容易发现是个dp，设计状态，dp[i][j]表示前i个数和为j的情况存不存在。存在就是1，不存在就是0，一开始再想能不能压成一维，其实是不可以的，因为最后要求的是n个数的和，如果压成一维就没办法确保是n个数的和了。

#include<bits/stdc++.h>
using namespace std;
int n,y;
int a[100010],b[100010];
bool dp[100010][110];//表示前i个数里和为j时，二维dp
{
    cin>>n>>y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    } 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
    }
    dp[1][a[1]]=1;
    dp[1][(a[1]+b[1])%y]=1;
    dp[1][(a[1]-b[1])%y]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=101;j++)//前i个数里和为j的情况 
        {
            if(dp[i-1][j])//有才能转移
            {
                dp[i][(j+a[i])%y]=1;
                dp[i][(j+a[i]+b[i])%y]=1;
                dp[i][(j+a[i]-b[i])%y]=1;
            } 
        }
    }
    for(int i=101;i>=0;i--) 
    {
        if(dp[n][i])
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}