题意
给定 $n$ 个区,每个区的价值为 $z_i$ ,现在有两个人竞争,我们想让第一个人赢,现在每个人每个区的支持人数分别为 $u,v$ ,哪方支持人数多,那么他就能获得这个区的价值,最后如果要使的第一个人获得的价值大于的二个人获得的价值,需要至少让多少人更改支持方。
思路
相当于就是说要选一些区的人改票,这能让我们想到背包DP,第一个人需要改票的人数为 $w_i$,显然 $w_i=\frac{u+v+1}{2}-u$,这相当于是背包容量,$z_i$ 即是背包物品价值。
转移方程如下:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<bits/stdc++.h> #define endl "\n" using namespace std; template<typename P> inline void read(P &x){ P res=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ res=res*10+ch-'0'; ch=getchar(); } x=res*f; } int T=1; int n,m; int w[120],z[120]; long long dp[100010]; signed main(){ read(n); int u,v,c=0; long long res=0x3f3f3f3f3f3f3f3f; memset(dp,0x3f,sizeof(dp)); for(int i=0;i<n;++i){ read(u),read(v),read(z[i]); if(u<v) w[i]=(u+v+1)/2-u; c+=z[i]; } dp[0]=0; for(int i=0;i<n;++i){ for(int j=c;j>=z[i];--j){ dp[j]=min(dp[j-z[i]]+w[i],dp[j]); } } for(int i=(c+1)/2;i<=c;++i) res=min(res,dp[i]); cout<<res<<endl; return 0; }
|