馅饼问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 330;

LL sum;
LL dp[maxn];
LL a[maxn];

int main(void)
{
    int n, m;
	LL res;
    while(scanf("%d", &n) != EOF)
    {
        memset(dp, -1, sizeof(dp));
		
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
		}
		dp[n] = a[n];
		sum = a[n];
		for(int i = n-1; i >= 1; i--){
			sum += a[i];
			dp[i] = max(dp[i+1], sum-dp[i+1]);
		}
		printf("%lld %lld\n",sum-dp[1],dp[1]);
    }
    return 0;
}

参考

https://blog.csdn.net/zhangtingxiqwq/article/details/133362167

https://zhuanlan.zhihu.com/p/288812473?utm_id=0

https://blog.csdn.net/luomingjun12315/article/details/45479073