題目鏈接：點擊查看

題目大意：給出n個餡餅，現在給出一個令牌，規定持有令牌的人可以選擇當前的餡餅給誰，然后下一輪令牌給沒有拿到餡餅的人，如此往復，一開始鮑勃拿著令牌，問最后兩人能吃到多少餡餅，兩人肯定都會采取最優策略玩游戲

題目分析：說是博弈，其實就是一個dp。。我的dp還是菜啊，訓練完之后zx學長給我講了一下就豁然開朗的，先別說我能不能推出來轉移方程了，我一開始都壓根沒想到這是一個動態規劃的題目，自閉了真的

回到這個題目，我們規定dp[i]為持有令牌的人獲得的餡餅數（該數目肯定是最優解），然后因為我們只知道初始時鮑勃拿著令牌，所以我們可以倒著轉移狀態，從dp[n]開始，這樣最后鮑勃和愛麗絲的答案分別就是dp[1]和sum-dp[1]了，在狀態轉移的過程中我們需要用到一個后綴和sum來輔助進行，sum[i]代表的就是第i個數到第n個數累加之和，因為每個位置持有令牌的人都可以選擇將當前餡餅給自己或給對手，那么我們的狀態可以簡單表示為拿或不拿，也就有了dp[i]=max(拿a[i],不拿a[i])，就有了下面的方程：

dp[i]=max(dp[i+1],a[i]+sum[i+1]-dp[i+1])

我反正dp菜死了，在加上平時dp全都扔給隊友。。所以自己是肯定做不出來的了

剩下的就是代碼實現了：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=60;int a[N];int dp[N];int sum[N];int main() { // freopen("input.txt","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=n;i>=1;i--)sum[i]=sum[i+1]+a[i];for(int i=n;i>=1;i--)dp[i]=max(dp[i+1],a[i]+sum[i+1]-dp[i+1]);cout<<sum[1]-dp[1]<<' '<<dp[1]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 859C Pie Rules(dp+博弈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。