「BZOJ2101」[Usaco2010 Dec] Treasure Chest 藏宝箱
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)
题解
直接复制了个题解
首先O(N^2)的DP挺好想的.
f[i,j]=sum[i,j]-min(f[i+1,j],f[i,j-1]).
但题目把n出到5000,内存卡到64M,二维的状态存不下..
其实,j这一维可以省掉.我们换个状态表示
f[i,i+len]=sum[i,i+len]-min(f[i+1,i+len],f[i,i+len-1])
然后循环这样写:
for len=1 to n
for i=1 to n-len.
容易看出第二维可以省掉了.
|
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 27 28 29 30 31 32 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int s[5005],f[5005]; int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); s[i]=s[i-1]+x; f[i]=x; } for(int l=1;l<n;l++) for(int i=1;i<=n-l;i++) f[i]=s[i+l]-s[i-1]-min(f[i],f[i+1]); printf("%d",f[1]); return 0; } |
OI 课件=>
