Hdu 6804 Contest of Rope Pulling —— 随机化，背包周期

本文主要是介绍Hdu 6804 Contest of Rope Pulling —— 随机化，背包周期，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有两个集合的人，每个人都有一个重量和一个价值，你要在每个集合中选择一些人使得两个集合的人的重量之和相同，并且总价值最大。

题解：

题解的想法我在赛场上也想到了，但是我是按照重量排序的，然后就被卡掉，过不去。
但是将所有人放在一起随机化一下的话，我们知道背包就是选择一些数使得他们的重量达到预定的大小的同时让价值之和最大。这道题目就是一个正向背包加一个反向背包使得他们在重量之和为0的情况下价值最大。
那么不妨设第二个集合的人的重量为负的，然后加到第一个集合当中，那么我们现在所要做的就是选择一些人使得重量之和为0，价值之和最大。然后随机化的话，就可以将正负更加离散的排列，更正确的说，是将正的我们要取的人和负的我们要取的人更离散的排列，这样我们在做背包的时候，可以将重量大概率地控制在一个范围内：
在这里插入图片描述
假设0点在这，那么随机以后，它的背包可能就会是这样的。当然，其中会多出很多无用的点，但是背包会记录所有情况，我们不需要知道到底是哪些有用的，哪些没用的。
mt19937可以随机一个在-MAXINT~MAXINT之间的值

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1005,ad=N*40;
ll dp[N*105];
mt19937 rnd(time(NULL));
struct node{int w;ll v;
}a[N*2];
int main()
{int t;scanf("%d",&t);while(t--){memset(dp,-1,sizeof(dp));int n,m;scanf("%d%d",&n,&m);n+=m;for(int i=1;i<=n;i++)scanf("%d%lld",&a[i].w,&a[i].v),a[i].w*=i>n-m?-1:1;shuffle(a+1,a+1+n,rnd);int l=ad,r=ad,liml=0,limr=ad*2;//ll ans=0;dp[ad]=0;for(int i=1;i<=n;i++){if(a[i].w>0){for(int j=r;j>=l;j--)if(~dp[j])dp[j+a[i].w]=max(dp[j+a[i].w],dp[j]+a[i].v);r=min(limr,r+a[i].w);}else{for(int j=max(-a[i].w,l);j<=r;j++)if(~dp[j])dp[j+a[i].w]=max(dp[j+a[i].w],dp[j]+a[i].v);l=max(liml,l+a[i].w);}}printf("%lld\n",dp[ad]);}return 0;
}