题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2101
题意:
共有n枚金币,第i枚金币的价值是w[i]。
把金币排成一条直线,Bessie和Bonny轮流取金币,看谁取到的钱最多。
Bessie先取,每次只能取一枚金币,而且只能选择取直线两头的金币,不能取走中间的金币。当所有金币取完之后,游戏就结束了。
Bessie和Bonny都是非常聪明的,她们会采用最好的办法让自己取到的金币最多。
请帮助Bessie计算一下,她能拿到多少钱?
题解:
区间dp共有两种表示状态的方法:
(1)dp[i][j]:表示区间[i,j]的答案。
一般转移为:dp[i][j] = best(dp[i+1][j], dp[i][j-1])
(2)dp[i][j]:左端点为i,区间长度为j。
一般转移为:dp[i][j] = best(dp[i][j-1], dp[i+1][j-1])
显然,第二种是可以压维的。因为dp[i][j]只与dp[...][j-1]有关。
在此题中,第一种表示会炸空间,所以只能用第二种。
表示状态:
dp[i][j] = max wealth
i:起点为i
j:区间长度为j
表示对于当前区间,先手的最大获利。
找出答案:
ans = dp[1][n]
表示整个区间。
如何转移:
对于一个区间,这个区间内的价值总和是一定的。
那么如果要让自己获利更大,就是要让对方接下来的获利最小。
自己的获利 = 区间价值总和 - 对方获利
即:dp[i][j] = sum(i,i+j-1) - min(dp[i][j-1], dp[i+1][j-1])
边界条件:
dp[i][1] = w[i]
只能拿走剩下的一个硬币。
优化:
压维。
前缀和。
AC Code:
// state expression:
// dp[i][j] = max wealth
// i: start pos
// j: len of present section
//
// find the answer:
// dp[1][n]
//
// transferring:
// dp[i][j] = sum(i,i+j-1) - min(dp[i][j-1], dp[i+1][j-1])
//
// boundary:
// dp[i][1] = w[i]
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 5005 using namespace std; int n;
int w[MAX_N];
int dp[MAX_N];
int sum[MAX_N]; void read()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>w[i];
}
} void cal_sum()
{
sum[]=;
for(int i=;i<=n;i++)
{
sum[i]=sum[i-]+w[i];
}
} void solve()
{
cal_sum();
for(int j=;j<=n;j++)
{
for(int i=;i<=n;i++)
{
if(j==) dp[i]=w[i];
else dp[i]=sum[i+j-]-sum[i-]-min(dp[i],dp[i+]);
}
}
} void print()
{
cout<<dp[]<<endl;
} int main()
{
read();
solve();
print();
}