USACO 3.3 A Game


动态规划法。
用dp[player][start][end]表示player在[start..end]会取得的最大值。
如果player==0,那么player有主动权,它要么选start,要么选end.显然,它要选使得对手得分最少的那一个。
当它选start时,对手所能到的最大值为dp[1][start+1][end]。当它选end时,对手所选的最大值是dp[1][start][end-1].
。所以我们选dp[1][start+1][end]和dp[1][start][end-1]中小的那一个。
如果player==1,那只能被动的等0先选了。1在剩下区段中,又作为先选的角色,即player0。
当只有一个数字的时候,player0就只有选这个,player1就没得选,返回0.
代码如下:

#include <iostream>
#include 
<fstream>

using namespace std;

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

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int dp[2][100][100];
int sequence[100];

int score(int player,int start,int end)
{
    
if(dp[player][start][end]!=-1)
        
return dp[player][start][end];

    
if(start==end){
        
if(player==0)
            dp[player][start][end] 
= sequence[start];
        
else 
            dp[player][start][end] 
= 0;
    }
else{
        
int t1 = score(0,start+1,end);
        
int t2 = score(0,start,end-1);
        
if(player==0){
            
if(t1>t2){
                dp[player][start][end] 
= sequence[end]+score(1,start,end-1);
            }
else{
                dp[player][start][end] 
= sequence[start]+score(1,start+1,end);
            }
        }
else{
            
if(t1>t2){
                dp[player][start][end] 
= score(0,start,end-1);
            }
else{
                dp[player][start][end] 
= score(0,start+1,end);
            }
        }
    }

    
return dp[player][start][end];
}

void solve()
{
    memset(dp,
-1,sizeof(dp));

    
int size;
    
in>>size;

    
for(int i=0;i<size;++i)
        
in>>sequence[i];

    
out<<score(0,0,size-1)<<" "<<score(1,0,size-1)<<endl;
}

int main(int argc,char *argv[])
{
    solve(); 
    
return 0;
}


posted on 2009-07-09 13:50 YZY 阅读(268) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO动态规划


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


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜