题目链接: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();
}
05-11 04:09
查看更多