dp 動态規劃 蘑菇

蘑菇真的貴，友情價更高  

Description

由于提莫為巡邏準備的蘑菇太多了，多餘的蘑菇路上種不下，于是他精心挑選了一些蘑菇拜訪他的好朋友小炮

提莫的蘑菇一共有n個，對于編号為i的蘑菇魔力值是ai。蘑菇的魔力值越高，小炮就越喜歡。當然因為二人是好朋友，蘑菇魔力值最低也不會小于0

提莫要與小炮分享這些蘑菇，他們制定了一個因吹斯聽的配置設定規則：

1. 兩人按1-n的順序逐個配置設定每個蘑菇的歸屬權
2. 對于一個蘑菇，如果這一輪的配置設定者将這個蘑菇分給自己，那麼下一輪配置設定權将轉讓給對方
3. 反之，如果配置設定者将蘑菇配置設定給對方，下一輪他還将持有配置設定權

你可能會以為提莫會讓着小炮，不你想多了！愛惡作劇的提莫會盡力讓小炮所獲得的蘑菇的魔力值的總和盡可能小！（友盡警告

請你幫小炮算算，如果小炮先手配置設定，他所能獲得的蘑菇的魔力值之和的最大值會是多少？

注意：提莫和小炮都足夠聰明且均采取最優政策

Input

單組輸入

第一行輸入一個n，代表物品的數量，1 <= n <= 3e5

第二行輸入n個數字a1-an，代表這n個蘑菇的魔力值，0 <= ai <= 1e9

Output

一個數字，小炮所能獲得的蘑菇的魔力值之和的最大值。

Sample Input 1

2
10 20      

Sample Output 1

20      

Hint

對于樣例1，小炮可以要走第一個蘑菇，提莫拿走第二個蘑菇，小炮的喜愛程度是10

小炮也可以把第一個蘑菇給提莫，繼續持有第二個蘑菇的配置設定權，然後拿走第二個蘑菇喜愛程度是20

是以小炮能拿到蘑菇的最大喜愛程度是20

Source

2019年集訓隊選拔賽

    這個題目，我不會，别人教我的，這個隻能從後面往前面推，至于為什麼，我也不知道，好像是從前面往後面會有後效性，你可以試試3   3 2 1 從前往後推就不對，從後往前就對了    

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;
ll sum[maxn], dp[maxn],dp1[maxn],a[maxn];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &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], dp1[i + 1]+a[i]);
		dp1[i] = sum[i] - dp[i];
	}
	printf("%lld\n", dp[1]);
	return 0;
}
           

　　

轉載于:https://www.cnblogs.com/EchoZQN/p/10487226.html