青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

USACO Section 3.3 A Game

A Game

IOI'96 - Day 1

Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents.

Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2.

PROGRAM NAME: game1

INPUT FORMAT

Line 1: N, the size of the board
Line 2-etc: N integers in the range (1..200) that are the contents of the game board, from left to right

SAMPLE INPUT (file game1.in)

6
4 7 2 9
5 2

OUTPUT FORMAT

Two space-separated integers on a line: the score of Player 1 followed by the score of Player 2.

SAMPLE OUTPUT (file game1.out)

18 11

Analysis

A typical game theory problem. The problem aims to find a solution for two players, which impletement optimal strategy for player 2. Considering the fact of only two operations for each step, making dynamic programming is helpful for these. F[i][j] is defined as the maximum sum for player 1 when choosing numbers among range [i,j], and s[i][j] stands for the sum of numbers among ith number and jth number. After all, new an array num[i] to store numbers.
Then, considering the two activities in choosing, which can only be happened for numbers of the first and the last one. Since the description needs an optimal strategy for player two, it is reasonable for maximum the result.
After all, the function can be presented below: f[i][j]=max{num[i]+sum[i+1][j]-f[i+1][j],num[j]+sum[i][j-1]-f[i][j-1]}, 1<=i,j<=n.
Initialization: f[i][i]=num[i], 1<=i<=n.
Tips in calculating: just only two variables: x,k. "j" is better fixed by x+k for f[i][j] is fully determined by f[i+1][j] and f[i][j-1], which are turing into f[x+1][x+k] and f[x][x+k-1]. It is obvious to making the first "for loop" of k and the next one is "x". Otherwise, i and j are too flexible to make loops.

Code

/*
ID:braytay1
PROG:game1
LANG:C++
*/

#include 
<iostream>
#include 
<fstream>
using namespace std;

int n;
int f[100][100],num[100],sum,s[100][100];

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


int main(){
    ifstream fin(
"game1.in");
    ofstream fout(
"game1.out");
    fin
>>n;
    
for(int i=0;i<n;i++) fin>>num[i];
    memset(f,
0,sizeof f);
    memset(s,
0,sizeof s);
    
for(int i=0;i<n;i++) f[i][i]=num[i];
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
            
for(int k=i;k<=j;k++)
                s[i][j]
+=num[k];
    
for(int k=1;k<n;k++)
        
for(int x=0;x+k<n;x++)        
            f[x][x
+k]=max(num[x]+s[x+1][x+k]-f[x+1][x+k],num[x+k]+s[x][x+k-1]-f[x][x+k-1]);
    fout
<<f[0][n-1]<<" "<<s[0][n-1]-f[0][n-1]<<endl;
    
return 0;
}


 

posted on 2008-09-01 16:36 幻浪天空領(lǐng)主 閱讀(249) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆檔案(2)

文章分類(23)

文章檔案(22)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久婷婷影院| 国产人久久人人人人爽| 国产精品永久| 亚洲欧美精品一区| 亚洲影院免费| 国产曰批免费观看久久久| 亚洲精品美女| 亚洲欧洲一二三| 免费日韩av电影| 亚洲激情专区| 亚洲国产日韩欧美在线动漫| 欧美激情视频在线免费观看 欧美视频免费一| 狠狠色噜噜狠狠色综合久 | 欧美1区2区| 日韩一区二区福利| 亚洲一区二区三区色| 国产一区二区三区av电影| 男人的天堂成人在线| 欧美国产欧美综合| 翔田千里一区二区| 猛男gaygay欧美视频| 野花国产精品入口| 性久久久久久久久久久久| 在线观看欧美黄色| 制服诱惑一区二区| 影音先锋日韩精品| 一区二区精品在线| 亚洲第一网站免费视频| 在线一区二区三区四区| 在线欧美电影| 一区二区三区四区五区视频| 国产一区二区无遮挡| 最新亚洲电影| 国产专区综合网| 亚洲最新色图| 最新国产の精品合集bt伙计| 亚洲一区二区欧美日韩| 亚洲精品护士| 久久久91精品国产| 亚洲免费婷婷| 欧美精品乱码久久久久久按摩| 亚洲欧美美女| 欧美激情一区二区三区在线视频观看| 欧美一区在线直播| 欧美日韩一区在线视频| 亚洲成人在线网| 精品动漫3d一区二区三区| 亚洲私人黄色宅男| 一区二区三区免费看| 免费日韩一区二区| 免费在线欧美黄色| 国产综合色产在线精品| 亚洲永久在线观看| 亚洲免费在线精品一区| 欧美日韩国产一区精品一区| 欧美二区乱c少妇| 欲色影视综合吧| 久久riav二区三区| 久久精品欧洲| 国产欧美视频一区二区| 亚洲视频网站在线观看| 亚洲视频一区二区| 欧美日本精品一区二区三区| 亚洲大胆女人| 亚洲人成在线播放| 欧美激情视频给我| 亚洲国产日韩欧美在线图片| 日韩视频永久免费观看| 欧美成人蜜桃| 亚洲日本无吗高清不卡| 亚洲精品裸体| 欧美日韩综合另类| 99国产精品久久久久久久成人热| 一二美女精品欧洲| 欧美日韩一区在线观看| 在线综合亚洲欧美在线视频| 亚洲一区激情| 国产三级精品在线不卡| 欧美在线亚洲综合一区| 久久久五月天| 亚洲激情第一区| 欧美精品一区二区三区四区| 99国产精品国产精品毛片| 亚洲欧美精品中文字幕在线| 国产精品一区二区三区久久| 欧美中文字幕在线播放| 欧美69视频| 在线综合亚洲| 国产视频在线观看一区 | 亚洲欧洲日本一区二区三区| 中国女人久久久| 国产日本欧美在线观看| 久久久精品动漫| 亚洲精品在线视频观看| 香蕉久久国产| 亚洲第一中文字幕| 国产精品久久波多野结衣| 欧美影院成人| 亚洲人成艺术| 久久精品日产第一区二区| 亚洲福利视频在线| 国产精品护士白丝一区av| 久久久精品国产99久久精品芒果| 亚洲精品色图| 久久久久欧美| 亚洲深夜福利视频| 伊人久久综合| 国产欧美不卡| 欧美巨乳在线观看| 久久婷婷蜜乳一本欲蜜臀| 正在播放亚洲| 亚洲精品人人| 麻豆精品网站| 欧美有码在线视频| 制服丝袜亚洲播放| 亚洲欧洲精品一区二区三区波多野1战4 | 亚洲欧美在线看| 亚洲三级电影在线观看| 国产亚洲欧美一区二区三区| 欧美日韩国产小视频| 六十路精品视频| 欧美一区二区三区男人的天堂| 亚洲欧洲一区二区三区| 免费一级欧美在线大片| 欧美在线首页| 亚洲图片欧洲图片av| 亚洲精品中文字| 1024成人| 黄页网站一区| 国内精品**久久毛片app| 国产精品五区| 国产精品高清在线| 欧美天堂亚洲电影院在线播放| 欧美大片在线看免费观看| 久久久久久久久伊人| 欧美一级视频精品观看| 亚洲综合国产| 亚洲综合视频一区| 欧美一区二区免费视频| 亚洲欧美日韩综合aⅴ视频| 一本久久青青| 亚洲深夜福利| 亚洲一区二区三区免费观看| 亚洲色在线视频| 亚洲婷婷国产精品电影人久久| 日韩一区二区高清| 一区二区不卡在线视频 午夜欧美不卡' | 一区二区三区在线观看欧美| 国产日韩精品在线| 国产日韩欧美一区二区三区四区| 国产精品资源| 国产一区二区三区在线观看免费| 国产午夜精品视频| 极品尤物av久久免费看 | 欧美日韩黄视频| 国产精品igao视频网网址不卡日韩| 国产精品久久久久999| 国产精品三区www17con| 国产专区综合网| 亚洲黄网站在线观看| 亚洲毛片av| 亚洲欧美国产日韩中文字幕| 欧美一区二区三区男人的天堂| 久久精品九九| 亚洲电影免费观看高清完整版| 亚洲国产精品传媒在线观看| 99精品视频网| 欧美一级淫片aaaaaaa视频| 可以看av的网站久久看| 欧美日韩高清区| 国产人久久人人人人爽| 亚洲国产欧美一区二区三区同亚洲| 一本色道久久| 久久久91精品国产| 亚洲电影毛片| 香蕉成人啪国产精品视频综合网| 美女图片一区二区| 欧美性做爰猛烈叫床潮| 亚洲国产高清高潮精品美女| 一区二区三区欧美在线| 久久一区二区三区四区五区| 亚洲欧洲久久| 久久―日本道色综合久久| 欧美天天在线| 在线国产精品播放| 午夜亚洲伦理| 亚洲国产一区二区视频| 欧美一区二区精品| 欧美日韩一区二区三区高清| 国产专区欧美专区| 亚洲欧美韩国| 欧美激情在线有限公司| 欧美亚洲色图校园春色| 欧美精品福利在线| 精品成人在线| 欧美在线播放高清精品| 99热在这里有精品免费| 久久亚洲综合色一区二区三区| 国产精品视区| 中文久久乱码一区二区|