每日一题 6月10日 失衡天平 DP

题目链接：https://ac.nowcoder.com/discuss/437998
题目大意：

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int a[105];
int f[105][200005];
int main(){

    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }

    f[0][100000]=1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=200000; j++){
            f[i][j]=max(f[i][j], f[i-1][j]);
            if(f[i-1][j]){
                f[i][j+a[i]]=max(f[i][j+a[i]], f[i-1][j]+a[i]);
                f[i][j-a[i]]=max(f[i][j-a[i]], f[i-1][j]+a[i]);
            }
        }
    }
    int ans=0;
    for(int i=-m; i<=m; i++){
        ans=max(ans, f[n][i+100000]-1);
    }
    printf("%d\n", ans);

    return 0;
}