(luogu3004) 宝箱 (USACO10DEC)

发表于 分类于 ，

一道 dp 的博弈题

【题目描述】

n 个硬币排成一行，每个硬币有一个价值 Ci, 两个人轮流取硬币

规定每个人每次只能拿走剩余硬币中最左边或最右边的硬币， 若硬币全部取完，游戏结束

求当两边都完美操作时先手能取得的硬币总和的最大值

思路:

区间 dp

设 d (l,r) 为在区间 [l,r] 上的最优解， 则对手的最优解为 d (l+1,r) 和 d (l,r-1) 的最大值

那么就有 d(l,r) = max(sum(l,r)-d(l+1,r),sum(l,r)-d(l,r-1))

即在对手剩下的局面中选择最优解

由于要求先手的最优解，所以答案为 d (1,n)

代码实现:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Mn(5005);
int d[Mn][Mn];
int s[Mn]; //前缀和优化区间和
int f(int l,int r) //记忆化搜索
{
    if(d[l][r])	return d[l][r];
    else
    {
        if(l==r)	return d[l][r] = s[r]-s[l-1];
        else
            return d[l][r] = max(s[r]-s[l-1]-f(l,r-1),s[r]-s[l-1]-f(l+1,r));
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i(1);i<=n;++i)
        scanf("%d",&s[i]), s[i]+=s[i-1];
    cout << f(1,n);
    return 0;
}