Stone game（dp计数上海icpc网络预选赛）

本文主要是介绍Stone game（dp计数上海icpc网络预选赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
都说是很简单的dp，可能对于会dp的人来说确实是很简单的dp。但是我们队一个会的也没有，太菜了。。
根据题目的要求，我们只需要枚举当前的最小值，那么我们由大到小排序，然后倒着找，这样当前值一定是最小的。根据题意我们会找出一个符合题意的范围。然后计算出如果当前石头为最小值的话，总共有多少种方案，然后更新答案。类似于01背包
代码如下：

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;const int maxx=3e2+100;
const int maxm=2e5+100;
int a[maxx];
ll dp[maxm];
int n;int main()
{int t,_min,_max;scanf("%d",&t);while(t--){scanf("%d",&n);int sum=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];for(int i=1;i<=sum;i++) dp[i]=0;dp[0]=1;sort(a+1,a+1+n);ll ans=0;for(int i=n;i>=1;i--){_min=(sum+1)/2-a[i];_max=(sum+a[i])/2-a[i];//这就是当前值为最小值的情况下，符合条件的范围数。for(int j=_min;j<=_max;j++) ans=(ans+dp[j])%mod;for(int j=sum;j>=a[i];j--)//这里类似于01背包，倒着找，不断更新。dp[j]代表的是总重量为j的方案数。{if(j<0) break;dp[j]+=dp[j-a[i]];dp[j]%=mod;}}printf("%lld\n",ans);}
}

努力加油a啊，(^o)/~

这篇关于Stone game（dp计数上海icpc网络预选赛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---