把题目转换成 x+y=z abs(x-y)<=k 的形式。x代表天平的一侧,y代表天平的另外一侧。 就变成了 把一些物品分成两堆,两堆的差小于等于k 。并且两边的物品不相同。 - -然后用到dp。修改一下的dp。 对于每一个可行解i。去寻找(i+m)/2 到(i+m)/2-m 的区间内是否可以组合。 然后为了避免冲突,将大于(i+m)/2 的 数字在dp中删除。之后再检查i是否存在。 如果存在就查找区间。区间内存在就是最大值。 #include <bits/stdc++.h> using namespace std; #define mo 100054 int a[mo]; int dp[mo]; int main() { int n,m; while(cin>>n>>m) { memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); dp[0]=0; for(int i=0;i<n;i++) { for(int j=10000;j>=a[i];j--) { if(dp[j-a[i]]|j==a[i]) dp[j]++;//增加组合类型数量 } } int maxs=0; int l=n-1; for(int i=10000;i>=0;i--) { if(dp[i]) { int q=(i+m)/2; while(a[l]>q&&l) { for(int j=i;j>=a[l];j--) if(dp[j-a[l]]||j==a[l]) dp[j]--;//将大于(i+m)/2 的值从dp空间中删除。然后看剩余的组合 l--; } // cout<<q<<' '<<l<<' '<<dp[i]<<' '<<i<<endl; if(dp[i]) for(int j=q;j>=q-m;j--)//查询区间是否有值 { if(dp[j]&&abs((i-j)-j)<=m) { maxs=max(i,maxs); // cout<<i<<' '<<j<<endl; } } } } cout<<maxs<<endl; } }
全部评论
(0) 回帖