Stone game-2019icpc上海网络赛 2019-09-17 算法竞赛 暂无评论 87 次阅读 题目链接: [https://nanti.jisuanke.com/t/41420](https://nanti.jisuanke.com/t/41420).  ## 题意： n个石头，每个石头有一个重量ai, 所有石头重量之和为S， 要求从中选一些石头，被选石头重量和为S', 满足S' >=S-S' 且 从S'中去掉任何一个石头，上式不成立，也就是选的石头的重量和刚好>=总重量的一半。问共有多少种选择方案。 ## 思路： 设总重量为Sum, 所选石头质量和为S' , 所选石头中最小值为min. 则已选石头重量和S' 与剩下未选石头重量和之差<= 已选石头中的最小值，即 S'-(Sum-S')<= min; 差值 d = S'-(Sum-S')=2*S'-Sum <=min(d>=0) Sum <= 2\*S' <=Sum+min 把重量ai 按降序排列，当以ai 为最小值时，只能选ai 左边的 ，ai 作为最小值是一定选的，其他的不确定选不选 设 S2 为所选石头除了ai 的重量和 S2=S' - ai Sum <= 2\*S' = 2\*S2 + 2\*ai <= Sum+min = Sum+ai 即 Sum- 2\*ai <= 2\*S2 <= Sum - ai 设dp[i][j] 表示 以i 为最小值 Sum=j 的方案数 dp[ i ][ j ] = dp[ i-1 ][ j ] +dp[ i-1 ][ j-a[-1] ] -------- ( j >= a[i-1] ) dp[ i ][ j ] = dp[ i-1 ][ j ] ---------------------- ----------( j < a[i-1] ) 对于每个i 所有满足 Sum- 2\*ai <= 2 \* j <= Sum - ai 的 dp[ i ][ j ] 加到ans 中 第一维i 可以略去 用滚动数组维护 ## 代码如下 ```c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+10; const int Mod=1e9+7; int t,n; int dp[1000000]; int a[N]; bool cmp(int a,int b) { return a>b; } int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); ll sum=0,ans=0; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a+1,a+n+1,cmp); memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1; i<=n; i++) { int l=sum-2*a[i]; int r=sum-a[i]; for(int j=150000; j>=1; j--) { if(j>=a[i-1]) dp[j]=(dp[j]+dp[j-a[i-1]])%Mod; if(j*2<=r&&j*2>=l) ans=(ans+dp[j]%Mod)%Mod; } if(l<=0&&r>=0) ans++; } printf("%d\n",ans); } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭