【每日一题】 失衡天平

动态规划。

首先，题目说不限操作次数，但其实只要操作一次即可，因为每次操作得到的两堆重量差值均<=m，只要将每次得到的两堆按大小互补的方式与前一次的两堆合并到一起即可，最后相当于得到一次操作的结果。

其次，动态规划。
原问题：从n个物品中选出两堆重量差不超过m时最大重量和。
子问题：从前i个物品选出两堆重量差不超过j时最大重量和。
描述：记dp[i][j]表示从前i个物品选出两堆重量差不超过j时最大重量和。
分析状态之间的关系，对于第i个物品，有如下几种可能的情况：
不选取，dp[i][j]=dp[i-1][j];
加在大堆，dp[i][j]=dp[i-1][j-ar[i]]+ar[i];
加在小堆，加后重量不超大堆，dp[i][j]=dp[i-1][j+ar[i]]+ar[i];
加在小堆，加后重量超过大堆，dp[i][j]=dp[i-1][ar[i]-j]+ar[i]。
如上情况取最大值即可。

最后有几点要注意：
j的取值范围并不是<=m，例如示例一，若取值范围为<=m则在考虑第三个物品时，61无法加到5上，因为不论另一堆是0还是1，差值都超出了m，所以应该将j的取值范围调整到最大差值(1e4)；
输出的答案并不是dp[n][m]，而是max{dp[n][j]},j<=m。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e2+9;
const int maxx=1e4+9;

int n,m,ar[maxn];
int dp[maxn][maxx];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>ar[i];
    for(int j=1;j<maxx;j++) dp[0][j]=-inf1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<maxx;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j+ar[i]]+ar[i]);
            if(ar[i]>=j) dp[i][j]=max(dp[i][j],dp[i-1][ar[i]-j]+ar[i]);
            if(ar[i]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-ar[i]]+ar[i]);
        }
    }
    int res=0;
    for(int j=0;j<=m;j++) res=max(res,dp[n][j]);
    cout<<res<<endl;
}