【BZOJ】2101: [Usaco2010 Dec]Treasure Chest 藏宝箱(dp)
http://www.lydsy.com/JudgeOnline/problem.php?id=2101
这个dp真是神思想orz
设状态f[i, j]表示i~j先手所拿最大值,注意,是先手
所以转移自然而然的变成
f[i, j]=sum[i, j]-min(f[i+1, j], f[i, j-1])
这个转移很好理解吧
但是本题开二维会mle。。
我们考虑以阶段来dp
我们发现,可以按长度为阶段
f[i, i+len]=sum[i, i+len]-min{f[i+1, i+len], f[i, i+len-1)}
而len是递增的,所以我们可以将第二维去掉,即变成滚动数组
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << #x << " = " << x << endl #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; } inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } inline const int max(const int &a, const int &b) { return a>b?a:b; } inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=5005; int a[N], n, ans, sum[N], f[N]; int main() { read(n); for1(i, 1, n) read(a[i]), sum[i]=sum[i-1]+a[i]; for2(l, 0, n) for1(i, 1, n-l) f[i]=sum[i+l]-sum[i-1]-min(f[i+1], f[i]); print(f[1]); return 0; }
Description
Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins. The N (1 <= N <= 5,000) coins, each with some value C_i (1 <= C_i <= 5,000) are placed in a straight line. Bessie and Bonnie take turns, and for each cow's turn, she takes exactly one coin off of either the left end or the right end of the line. The game ends when there are no coins left. Bessie and Bonnie are each trying to get as much wealth as possible for themselves. Bessie goes first. Help her figure out the maximum value she can win, assuming that both cows play optimally. Consider a game in which four coins are lined up with these values: 30 25 10 35 Consider this game sequence: Bessie Bonnie New Coin Player Side CoinValue Total Total Line Bessie Right 35 35 0 30 25 10 Bonnie Left 30 35 30 25 10 Bessie Left 25 60 30 10 Bonnie Right 10 60 40 -- This is the best game Bessie can play.
Input
* Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains a single integer: C_i
Output
* Line 1: A single integer, which is the greatest total value Bessie can win if both cows play optimally.
Sample Input
30
25
10
35
Sample Output
HINT
(贝西最好的取法是先取35,然后邦妮会取30,贝西再取25,邦妮最后取10)
Source
相关文章
- poj1159--Palindrome(dp:最长公共子序列变形 + 滚动数组)
- POJ 3254 简单状压DP
- hdu 3006 The Number of set(思维+壮压DP)
- BZOJ 3864 Hero meet devil DP套DP
- POJ 3280 Cheapest Palindrome (区间DP)
- UVa 10723 Cyborg Genes (LCS, DP)
- UVa 12186 Another Crisis (DP)
- BZOJ 3329 Xorequ 数字DP+矩阵乘法
- 【uoj#311】[UNR #2]积劳成疾 dp
- 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
- 【bzoj4580】[Usaco2016 Open]248 区间dp
- 【bzoj1688】[USACO2005 Open]Disease Manangement 疾病管理 状态压缩dp+背包dp