(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;
}