[每一]DP-类似背包

https://ac.nowcoder.com/acm/problem/19158

每件武器只有三种选择： 放在左边，或者放在右边，或者不放
对应着也就三种状态转移，考虑背包思想
dp[i][j] 表示前i个左右重量差为j的最大重量
则状态转移为：
不选：
选：
考虑质量差最大是所有武器重量总和，最小是0
代码如下：：：：：
（这题好像还行，不算难--=-=-=-

//AC
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105];
int dp[105][100005];//dp[i][j]  前i个左右重量差为j的最大重量
int main(){
    int n,k;
    cin>>n>>k;
    int tol = 0;
    for(int i = 1 ;i <= n ; ++i ){
        cin>>a[i];
        tol += a[i];
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ;++i){
        for(int j = 0 ; j <= tol ; ++j){
            dp[i][j] = dp[i-1][j];//不选
            int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);//放在左  或者 放在右
            dp[i][j] = max(dp[i][j],tmp+a[i]); // 合计。
        }
    }
    int ans = 0;
    for(int i = 0 ; i <= k ;++i){
        ans = max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
}