[USACO 2010 Dec S]Treasure Chest

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.

C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 480K, 提交时间: 2019-10-14 20:07:51

#include <bits/stdc++.h>
using namespace std;
int n,m,a,sum[5005],f[3][5005];
int main()
{
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a;
        sum[i]=sum[i-1]+a;
        f[1][i]=a;
    }
    for(int j=2; j<=n; ++j)
        for(int i=j; i>=1; --i)
            f[j&1][i]=sum[j]-sum[i-1]-min(f[!(j&1)][i],f[j&1][i+1]);
    cout<<f[n&1][1];
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 28ms, 内存消耗: 444K, 提交时间: 2023-03-24 17:58:44

#include<iostream>
using namespace std;

const int N=5005;
int dp[N],sum[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>dp[i];
		sum[i]=sum[i-1]+dp[i];
	}
	for(int i=2;i<=n;i++){
		for(int l=1;l+i-1<=n;l++){
			int r=l+i-1;
			dp[l]=sum[r]-sum[l-1]-min(dp[l],dp[l+1]);
		}
	}
	cout<<dp[1];
	
	return 0;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 272ms, 内存消耗: 476K, 提交时间: 2019-10-13 10:49:24

uses math;
var
a:array[0..2,0..5001] of longint;
b:array[0..5001] of longint;
m,n,i,j:longint;
begin
read(n);
for i:=1 to n do
 begin
  read(a[1,i]);
  b[i]:=b[i-1]+a[1,i];
 end;
for j:=2 to n do
 for i:=j downto 1 do
  a[j and 1,i]:=b[j]-b[i-1]-min(a[((j and 1)+1) mod 2,i],a[j and 1,i+1]);
writeln(a[n and 1,1]);
end.

详情