AlvinZH过生日 | Eternal_zttz

AlvinZH过生日

致敬DP

1. 解题思路

逆推DP.

解这道题的关键就在于dp的状态只和是否有选择权有关,而与选择权在谁手里无关。注意无论选择权在谁手里,他都会尽可能的获得最大的蛋糕重量。

dp[i]表示分配到第i个物品为止,当前拥有选择权的人能获得的最大蛋糕重量,即蛋糕[i~n]的最大值。以有选择权的的人列一个转移方程。因为我们只知道初始选择的是AlvinZH,因此我们要逆推:

f[i] = max(f[i+1], sum - f[i+1] + vl[i]);//max(不吃, 吃)

其中sum为[i+1~n]蛋糕总质量。如果不吃第i块蛋糕,那么自己仍然保留选择权,那么f[i] = f[i+1],如果选择吃了第i块,那么自己在接下来的蛋糕中,便只能吃sum- f[i+1]的值,所以f[i] = sum - f[i+1] + v[i];

最后dp[1]就是AlvinZH获得的最大价值。

注意:

注释里的吃与不吃并不是一直针对同一个人的,指的是当前有选择权的人对当前蛋糕吃与不吃。

整个过程没有管AlvinZH吃还是不吃,针对的对象是有选择权的那个人。

2. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int sum;
int v[110],f[110];
int main(){
while(~scanf("%d",&n)){
sum = 0;
memset(f, 0, sizeof(f));
for (int i = 1;i<=n;i++)
scanf("%d",&v[i]);
for (int i = n;i>=1;i--){
f[i] = max(f[i+1],sum-f[i+1]+v[i]);
sum += v[i];
}
printf("%d\n",f[1]);
}
}
-------------The End-------------