失衡天平 DP

一看题意首先想了求最值，那么就是二分 但是操作过程中是很灵活的，然后果断pass掉，然后DP，很明确题目就是三种情况，要么放左边，要么不放，要么放右边，反正最后取得的武器必然左右两边差值不过M，那么就要想DP方程式，DP[i][j]=代表前i个物品左右最多相差j的质量，我们可以很容易想到要是本次不放那么就是dp[i][j]=dp[i-1][j],直接就是继承上一次的，然后就是放左边，我们应该是dp[i][j+x]=max(dp[i-1][j]+x),放在右边那就是dp[i][abs(j-x)]=dp[i-1][j]+x;

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<x<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
ll gcd(ll a,ll b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
int ans[110];
int dp[110][10100];///dp[i][j]选择前面i个物品然后最大的差值为j
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
int main()
{
    int m,n;
    cin>>n>>m;
    int sum=0;
        mse(dp,-0x3f3f);
        dp[0][0]=0;
    for(it i=1;i<=n;i++)
        {
            cin>>ans[i];
            for(int j=0;j<=10000;j++)
        {
            int x=ans[i];
             dp[i][j] = max(dp[i][j], dp[i-1][j]);///左右都不加，直接继承上一次的
            if(j+ans[i]<=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);
        }
        }
        sum=0;
        for(int i=1;i<=m;i++)
           sum=max(sum,dp[n][i]);
        cout<<sum<<endl;
    return 0;
}