2020HDU多校第四场 Contest of Rope Pulling

题意：两班各选几人参加比赛，每个人都有体重和魅力值，要求在两边体重相等的情况下魅力值最大。

分析：01背包问题，不过直接写的话复杂度是O(10^9)显然不行。(比赛时有人竟然用容量和为上界水过了
官方题解的优化:
通过随机化算法进行优化背包容量。(random_shuffle)
将所有选手随机排列然后依次算背包，背包的容量限定在范围 中即可，而这个 足够大即可
题解证明:容量上界取： .

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=2e5+10;
const int up=1e5;
const ll inf=0x7f7f7f7f;

struct node{
    int w,v;
}a[maxn];

ll dp[2][maxn];

int main()
{
    int t,n,m;
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%d",&n,&m);
        for( int i=1;i<=n+m;i++ )
        {
            int w,v;scanf("%d%d",&w,&v);
            w= i>n ? -w : w;
            a[i]={w,v};
        }
        n+=m;

        random_shuffle(a+1,a+1+n);
    //    random_shuffle(a+1,a+1+n);

        int lim=sqrt(n)*1000;
        for(int i=0;i<=1;i++ )
        {
            for( int j=0;j<=2*up;j++ ) dp[i][j]=-1e18;
        }

        dp[0][up]=0;
        int op=1;
        for( int i=1;i<=n;i++ )
        {
            for( int j=-lim;j<=lim;j++ )
            {
                dp[op][j+a[i].w+up]=max( dp[op^1][j+a[i].w+up],dp[op^1][j+up]+a[i].v);
            }
            op^=1;
        }
        printf("%lld\n",dp[op^1][up]);
    }
    return 0;
}