題目鏈接
都說是很簡單的dp，可能對(duì)于會(huì)dp的人來說確實(shí)是很簡單的dp。但是我們隊(duì)一個(gè)會(huì)的也沒有，太菜了。。
根據(jù)題目的要求，我們只需要枚舉當(dāng)前的最小值，那么我們由大到小排序，然后倒著找，這樣當(dāng)前值一定是最小的。根據(jù)題意我們會(huì)找出一個(gè)符合題意的范圍。然后計(jì)算出如果當(dāng)前石頭為最小值的話，總共有多少種方案，然后更新答案。類似于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];//這就是當(dāng)前值為最小值的情況下，符合條件的范圍數(shù)。for(int j=_min;j<=_max;j++) ans=(ans+dp[j])%mod;for(int j=sum;j>=a[i];j--)//這里類似于01背包，倒著找，不斷更新。dp[j]代表的是總重量為j的方案數(shù)。{if(j<0) break;dp[j]+=dp[j-a[i]];dp[j]%=mod;}}printf("%lld\n",ans);} }

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

總結(jié)

以上是生活随笔為你收集整理的Stone game（dp计数上海icpc网络预选赛）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。