[NC19158]失衡天平

题解：动态规划我们设方程为dp[i][j]代表前i个元素相差j的时候最大的重量是多少。

dp[i][j]=max(dp[i-1][j],dp[i][j]);

dp[i][j+a[i]]=max(dp[i][j+a[i]],dp[i-1][j]+a[i]);
dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+a[i]);

今天的要由昨天的递推过来。
为什么会有一个j+a[i]和一个j-a[i]，
分别代表着把第i个物品放在同侧
和把第i个物品放在右侧。
这里的代码没用abs，所以开了一倍长的空间记录放在右侧的情况
特别注意一点就是起始点不能为0，也就是dp[0][10000]=0要有这句话

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 110;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;

int n,m;
int a[maxn];
int dp[110][20010];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=100;i++){
        for(int j=0;j<=20000;j++){
            dp[i][j]=MinN;
        }
    }
    dp[0][10000]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=20000;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
            if(j+a[i]<=20000) dp[i][j+a[i]]=max(dp[i][j+a[i]],dp[i-1][j]+a[i]);
            if(j-a[i]>=0) dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+a[i]);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,dp[n][10000+i]);
        ans=max(ans,dp[n][10000-i]);
    }

    cout<<ans<<endl;
    return 0;
}