USACO Section 3.3 Home on the Range - DP而已~

这道题算是USACO3.3里最水的一道了~~~1A啊~~思维也很简单~~从长度为1的一直推到长度为n的...

要更新长度为k的(l,r)的两人分数..首先看当前状态时谁来取..这里就和总个数做个差看下奇偶就可以了...具体更新到什么值就看(l+1,r)+data[l]与(l,r-1)+data[r]哪个更优~~

注意的是在更新时~~当前长度没更新的那个人的分数也要跟着传递~~

Program:

/* ID: zzyzzy12 LANG: C++ TASK: game1 */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; int n,i,k,a[205],dp[205][205][2]; int main() { freopen("game1.in","r",stdin); freopen("game1.out","w",stdout); scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); for (i=1;i<=n;i++) dp[i][i][(n-1)%2]=a[i]; int x,y; for (k=1;k<n;k++) for (x=1;x<=n-k;x++) { y=x+k; i=(n-k-1)%2; dp[x][y][i]=dp[x+1][y][i]+a[x]; dp[x][y][1-i]=dp[x+1][y][1-i]; if (dp[x][y][i]<dp[x][y-1][i]+a[y]) { dp[x][y][i]=dp[x][y-1][i]+a[y]; dp[x][y][1-i]=dp[x][y-1][1-i]; } } printf("%d %d\n",dp[1][n][0],dp[1][n][1]); return 0; }