977 AlvinZH過生日

思路

難題。逆推DP。

要明確dp的狀態只與是否有選擇權有關，而與選擇權在誰手里無關。因為不論選擇權在誰手里，那個人都會盡可能的獲得最大的蛋糕重量。

dp[i]表示分配到第i個物品為止，當前擁有選擇權的人能獲得的最大蛋糕重量，即蛋糕[i~n]的最大值。以有選擇權的的人列一個轉移方程，然而因為我們只知道初始選擇的是AlvinZH，因此我們要逆推：

dp[i] = max(dp[i+1], sum - dp[i+1] + val[i]);//max(不吃， 吃)

其中sum為[i+1~n]蛋糕總質量，最后dp[1]就是AlvinZH獲得的最大價值。

注意：

• 注釋里的吃與不吃并不是一直針對同一個人的，指的是當前有選擇權的人對當前蛋糕吃與不吃。
• 整個過程沒有管AlvinZH吃還是不吃，針對的對象是有選擇權的那個人。

分析

這道題很有意思，巧妙地避過了選擇權在誰手里的問題，dp求解的是有選擇權能獲得的最大價值，并沒有考慮誰有選擇權。

逆推也很有意思，因為只知道開始時選擇權在AlvinZH手里。

好好理解吧，神奇的DP，你對它一無所知。

參考代碼一

// // Created by AlvinZH on 2017/11/5. // Copyright (c) AlvinZH. All rights reserved. //#include <cstdio> #include <cstring> #include <iostream> using namespace std;int n; int sum;//表示i+1~n塊蛋糕的總量 int val[105], dp[105];int main() {while(~scanf("%d", &n)){sum = 0;memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i)scanf("%d", &val[i]);for(int i = n; i >= 1; --i){dp[i] = max(dp[i + 1], sum - dp[i + 1] + val[i]);//max(不吃, 吃)。sum += val[i];}printf("%d\n", dp[1]);} }

轉載于:https://www.cnblogs.com/AlvinZH/p/7867597.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的977 AlvinZH过生日（背包DP大作战S）的全部內容，希望文章能夠幫你解決所遇到的問題。

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