【每日一题】失衡天平

题目描述
终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好，这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）
输入描述:
第一行2个整数 n, m;
第二行n个整数x，分别表示n件武器的重量。
1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100;

思路
放置时操作多次其实和操作一次最终的效果是一样的
定义 dp[i][j] ，在第 i 个物品天平两边相差为 j 的最大收益
有三种情况
不选的情况

同侧

异侧

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int n,m;
int dp[105][10005];
void solve(){
    memset(dp,-INF,sizeof(dp));
    cin>>n>>m;
    int x;
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        cin>>x;
        for(int j=0;j<=10000;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            if(j+x<=10000)dp[i][j+x]=max(dp[i][j+x],dp[i-1][j]+x);
            dp[i][abs(j-x)]=max(dp[i][abs(j-x)],dp[i-1][j]+x);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,dp[n][i]);
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<endl;
    solve();
    return 0;
}