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

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>
            亚洲精品一品区二品区三品区| 欧美99久久| 亚洲特色特黄| 国产乱码精品1区2区3区| 久久动漫亚洲| 美女精品网站| 亚洲午夜羞羞片| 小黄鸭精品aⅴ导航网站入口| 国产一区二区精品久久91| 久久久久久久国产| 老司机午夜精品| 亚洲婷婷在线| 欧美在线视频在线播放完整版免费观看 | 久久久www成人免费毛片麻豆| 欧美图区在线视频| 久久国产手机看片| 欧美成人免费小视频| 亚洲——在线| 久久久国产视频91| 亚洲私人影院在线观看| 久久国产精品电影| 亚洲美女精品久久| 欧美一区二区精品在线| 日韩午夜电影av| 久久精品91| 亚洲欧美日韩成人| 免费毛片一区二区三区久久久| 亚洲午夜精品久久| 久久亚洲精品一区二区| 亚洲男人的天堂在线aⅴ视频| 久久裸体视频| 性欧美精品高清| 欧美日本中文字幕| 欧美成人69av| 国产在线不卡精品| 宅男噜噜噜66一区二区66| 亚洲国产欧美不卡在线观看| 在线综合亚洲| 洋洋av久久久久久久一区| 欧美在线首页| 翔田千里一区二区| 欧美日韩在线直播| 亚洲福利av| 国产综合视频| 香蕉久久夜色精品国产| 亚洲夜晚福利在线观看| 欧美a级在线| 美女黄网久久| 国色天香一区二区| 午夜久久久久久| 亚洲欧美日韩网| 欧美日韩精品免费| 亚洲精品一区在线| 日韩一二三在线视频播| 欧美成人国产一区二区| 欧美成人三级在线| 亚洲第一狼人社区| 老司机久久99久久精品播放免费| 久久国产主播精品| 国产亚洲精品一区二555| 小辣椒精品导航| 久久爱www.| 一区二区在线观看视频| 久久久久久综合| 免费精品99久久国产综合精品| 国产综合色产在线精品| 久久国产日韩| 麻豆精品视频在线观看视频| 亚洲成在人线av| 欧美高清不卡| 99热在线精品观看| 亚洲专区欧美专区| 国产欧美在线视频| 久久免费视频网站| 亚洲激情国产| 亚洲专区一区二区三区| 国产精品日韩在线| 欧美主播一区二区三区美女 久久精品人| 欧美在线地址| 在线观看日韩av电影| 欧美波霸影院| 一区二区三区视频在线| 久久高清国产| 亚洲国产欧美久久| 欧美三级网页| 久久精品二区| 亚洲人体影院| 欧美在线999| 亚洲电影视频在线| 欧美亚洲不卡| 久久蜜桃资源一区二区老牛 | 老色鬼精品视频在线观看播放| 在线播放日韩| 欧美视频三区在线播放| 校园春色综合网| 亚洲欧洲精品天堂一级| 亚洲女人av| 亚洲国产一区视频| 欧美性做爰猛烈叫床潮| 久久av资源网| 一本久久综合| 免费精品视频| 久久av资源网| 在线视频欧美日韩| 黄色在线成人| 国产精品日韩在线观看| 免费欧美日韩国产三级电影| 亚洲一区二区三区精品视频| 欧美成人午夜影院| 午夜一区二区三区在线观看| 亚洲精一区二区三区| 国产欧美一二三区| 欧美日本亚洲韩国国产| 久久久久久久一区| 亚洲一区二区三区免费在线观看| 欧美国产激情二区三区| 久久精品国产第一区二区三区| 亚洲视频1区| 亚洲精品国产精品国自产观看浪潮| 国产精品网曝门| 欧美日韩一区综合| 欧美精品一区二区三区很污很色的| 久久精品视频播放| 午夜亚洲精品| 亚洲深夜福利视频| 日韩视频一区二区三区在线播放免费观看 | 亚洲尤物视频在线| 亚洲第一页中文字幕| 久久精品99国产精品| 一本色道久久88综合亚洲精品ⅰ| 精品盗摄一区二区三区| 国产一区二区电影在线观看| 国产精品天天摸av网| 国产精品超碰97尤物18| 欧美日韩亚洲一区二区三区在线观看| 玖玖玖免费嫩草在线影院一区| 久久国产乱子精品免费女 | 欧美黄在线观看| 欧美成人在线免费观看| 久久久一本精品99久久精品66| 欧美一级夜夜爽| 欧美影院一区| 久久精品国产一区二区三区| 性娇小13――14欧美| 欧美一区二区三区四区高清 | 亚洲福利av| 亚洲国产成人tv| 91久久午夜| 99热免费精品| 午夜精品福利一区二区三区av | 亚洲午夜免费福利视频| 亚洲性色视频| 久久国产精品99国产精| 久久久综合香蕉尹人综合网| 毛片一区二区三区| 亚洲激情视频在线播放| 99re66热这里只有精品3直播| 中文日韩在线视频| 小黄鸭精品aⅴ导航网站入口| 欧美专区日韩专区| 美女国产一区| 国产精品vip| 黑人巨大精品欧美一区二区小视频| 136国产福利精品导航| 99re这里只有精品6| 亚洲一区二区精品| 久久久91精品| 91久久精品国产91性色 | 久久久精品动漫| 亚洲高清不卡在线| 亚洲影视在线播放| 久久婷婷色综合| 欧美午夜影院| 在线观看欧美亚洲| 亚洲欧美日韩精品久久亚洲区| 久久夜色精品国产欧美乱极品| 亚洲精品久久久久久久久久久久 | 亚洲一区二区三区高清不卡| 久久久久久999| 国产精品久久久久av| 在线观看成人小视频| 亚洲一区尤物| 亚洲高清视频在线| 午夜精品www| 欧美日韩国产另类不卡| 韩国一区二区三区美女美女秀| 夜夜嗨av一区二区三区免费区| 久久久www免费人成黑人精品| 亚洲区在线播放| 久久色在线播放| 国产欧美日韩综合精品二区| 亚洲免费av观看| 农村妇女精品| 久久xxxx| 国产精品区一区二区三| 日韩亚洲欧美综合| 欧美国产日本高清在线| 欧美一区日韩一区| 国产精品亚洲激情| 亚洲欧美韩国|