随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.3.4 A Game (博弈DP)

设num[i]表示第i个数，sum[i][j]表示num[i]到num[j]的和，dp[i][j]表示从i到j,先取数者可以得到的最大值。

状态转移方程：

dp[i][j] = max( num[i]+sum[i+1][j]-dp[i+1][j], num[j]+sum[i][j-1]-dp[i][j-1] );

/*
ID: lorelei3
TASK: game1
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAX = 250;
int num[MAX];
int sum[MAX][MAX], dp[MAX][MAX];

int n;

inline int max(int a, int b){
    return a>b?a:b;
}

int main(){

    int i,j,w;

    ifstream fin("game1.in");
    ofstream fout("game1.out");

    fin>>n;

    for(i=1; i<=n; ++i){
        fin>>num[i];
        dp[i][i]=num[i];
    }

    for(i=1; i<=n; ++i){
        sum[i][i] = num[i];
        for(j=i+1; j<=n; ++j)
            sum[i][j] = sum[i][j-1] + num[j];
    }

    for(w=1; w<n; ++w)
        for(i=1; i+w<=n; ++i)
            dp[i][i+w] = max(num[i]+sum[i+1][i+w]-dp[i+1][i+w], num[i+w]+sum[i][i+w-1]-dp[i][i+w-1]);

    
    fout<<dp[1][n]<<" "<<sum[1][n]-dp[1][n]<<endl;

    return 0;
}
posted on 2011-01-14 15:52 小阮 阅读(158) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮