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

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219404
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

Two Ends
Time Limit:1000MS? Memory Limit:65536K
Total Submit:625 Accepted:271

Description
In the two-player game "Two Ends", an even number of cards is laid out in a row. On each card, face up, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. Now one strategy is to simply pick the card at the end that is the largest -- we'll call this the greedy strategy. However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 3 instead of the 4.)
3 2 10 4
You are to determine exactly how bad the greedy strategy is for different games when the second player uses it but the first player is free to use any strategy she wishes.

Input
There will be multiple test cases. Each test case will be contained on one line. Each line will start with an even integer n followed by n positive integers. A value of n = 0 indicates end of input. You may assume that n is no more than 1000. Furthermore, you may assume that the sum of the numbers in the list does not exceed 1,000,000.

Output
For each test case you should print one line of output of the form:
In game m, the greedy strategy might lose by as many as p points.
where m is the number of the game (starting at game 1) and p is the maximum possible difference between the first player's score and second player's score when the second player uses the greedy strategy. When employing the greedy strategy, always take the larger end. If there is a tie, remove the left end.

Sample Input

4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0

Sample Output

In game 1, the greedy strategy might lose by as many as 7 points.
In game 2, the greedy strategy might lose by as many as 4 points.
In game 3, the greedy strategy might lose by as many as 5 points.

Source
East Central North America 2005

#include? < iostream >
#include?
< cmath >
using ? namespace ?std;

const ? int ?MAXN? = ? 1001 ;
int ?dp[MAXN][MAXN];

int ?main()
{
????
int ?i,?j,?l,?n;
????
int ?t? = ? 1 ;
????
int ?tmp;
????
int ?a[MAXN];
????
while ?(scanf( " %d " ,? & n),?n > 0 )
????
{
????????memset(dp,?
0 ,? sizeof (dp));
????????
for ?(i = 1 ;?i <= n;?i ++ )
????????????scanf(
" %d " ,? & a[i]);
????????????
????????
for ?(i = 1 ;?i < n;?i ++ )
????????????dp[i][i
+ 1 ]? = ?abs(a[i]? - ?a[i + 1 ]);
????????
for ?(l = 4 ;?l <= n;?l += 2 )
????????
{
????????????
for ?(i = 1 ;?i <= n - l + 1 ;?i ++ )
????????????
{
????????????????j?
= ?i? + ?l? - ? 1 ;
????????????????
if ?(a[j]? <= ?a[i + 1 ])
????????????????
{
????????????????????tmp?
= ?dp[i + 2 ][j]? + ?a[i]? - ?a[i + 1 ];
????????????????????
if ?(dp[i][j]? < ?tmp)
????????????????????????dp[i][j]?
= ?tmp;
????????????????}

????????????????
if ?(a[i]? < ?a[j - 1 ])
????????????????
{
????????????????????tmp?
= ?dp[i][j - 2 ]? + ?a[j]? - ?a[j - 1 ];
????????????????????
if ?(dp[i][j]? < ?tmp)
????????????????????????dp[i][j]?
= ?tmp;
????????????????}

????????????????
if ?(a[i]? >= ?a[j - 1 ])
????????????????
{
????????????????????tmp?
= ?dp[i + 1 ][j - 1 ]? + ?a[j]? - ?a[i];
????????????????????
if ?(dp[i][j]? < ?tmp)
????????????????????????dp[i][j]?
= ?tmp;
????????????????}

????????????????
if ?(a[j]? > ?a[i + 1 ])
????????????????
{
????????????????????tmp?
= ?dp[i + 1 ][j - 1 ]? + ?a[i]? - ?a[j];
????????????????????
if ?(dp[i][j]? < ?tmp)
????????????????????????dp[i][j]?
= ?tmp;
????????????????}

????????????}

????????}

????????printf(
" In?game?%d,?the?greedy?strategy?might?lose?by?as?many?as?%d?points.\n " ,?t ++ ,?dp[ 1 ][n]);
????}

????system(
" pause " );
????
return ? 0 ;
}

posted on 2006-08-28 16:00 閱讀(579) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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久久久久久人| 国产精品久久9| 羞羞色国产精品| 性欧美xxxx大乳国产app| 国产一区二区在线观看免费播放| 久久久久免费视频| 裸体一区二区| 亚洲午夜影视影院在线观看| 亚洲摸下面视频| 一区在线免费观看| 亚洲日韩中文字幕在线播放| 国产精品www.| 久久先锋影音| 欧美精品18videos性欧美| 亚洲欧美日韩综合| 久久九九全国免费精品观看| 亚洲国产精品va在看黑人| 日韩视频久久| 国语自产精品视频在线看8查询8| 欧美a级一区二区| 国产精品av久久久久久麻豆网| 久久电影一区| 欧美精品一卡二卡| 久久久久久999| 欧美日本免费一区二区三区| 久久精品欧美| 欧美精品激情blacked18| 久久国产精品久久久久久| 欧美国产激情二区三区| 欧美在线免费一级片| 欧美激情影院| 美女视频黄 久久| 欧美亚州韩日在线看免费版国语版| 久热精品视频在线| 国产精品视频xxxx| 亚洲片国产一区一级在线观看| 国产精品一区免费视频| 亚洲精品日日夜夜| 亚洲电影激情视频网站| 亚洲欧美日韩视频一区| 宅男噜噜噜66国产日韩在线观看| 久久精品亚洲国产奇米99| 亚洲天堂视频在线观看| 欧美国产日韩在线| 农村妇女精品| 国产一区二区三区四区三区四| 日韩系列在线| 日韩视频在线观看免费| 噜噜噜噜噜久久久久久91| 欧美在线播放| 国产麻豆日韩| 亚洲一区二区三区精品视频| 中日韩视频在线观看| 欧美精品xxxxbbbb| 亚洲国产精品一区二区第四页av | 久久阴道视频| 欧美在线视频在线播放完整版免费观看 | 一区二区高清| 一本色道久久88综合亚洲精品ⅰ| 狂野欧美激情性xxxx| 久久视频在线看| 韩曰欧美视频免费观看| 欧美一级播放| 久久精品成人一区二区三区蜜臀| 国产精品久久午夜夜伦鲁鲁| 亚洲午夜羞羞片| 香蕉免费一区二区三区在线观看| 国产精品高潮呻吟久久av无限| 99视频一区| 亚洲免费在线播放| 国产精品一级| 欧美一区二区三区在线免费观看| 久久激情婷婷| 亚洲国产黄色片| 欧美成人69| aa级大片欧美三级| 欧美在线视频日韩| 1024精品一区二区三区| 你懂的亚洲视频| 亚洲精品一区二区三| 亚洲伊人网站| 狠狠v欧美v日韩v亚洲ⅴ| 久久久久免费| 亚洲激情电影在线| 亚洲免费在线电影| 精品成人a区在线观看| 免费91麻豆精品国产自产在线观看| 亚洲欧洲三级| 欧美在线播放视频| 亚洲欧洲午夜| 国产精品久久久久一区二区三区共 | 先锋资源久久| 韩国美女久久| 欧美日韩国产探花| 久久九九国产精品| 亚洲伦伦在线| 久久野战av| aⅴ色国产欧美| 国产一区二区电影在线观看| 欧美高清在线精品一区| 亚洲欧美日韩国产成人精品影院| 免费日韩av| 午夜精品视频在线| 亚洲人体偷拍| 国产在线观看一区| 欧美视频成人| 美女91精品| 亚洲欧美在线一区| 日韩亚洲欧美成人一区| 欧美成人高清| 久久成人精品无人区| 9色porny自拍视频一区二区| 在线观看视频亚洲| 国产免费亚洲高清| 欧美日韩免费观看中文| 久久综合婷婷| 久久国产天堂福利天堂| 亚洲图片欧洲图片av| 亚洲人午夜精品| 欧美福利一区| 另类av导航| 久久精品欧洲| 欧美一区91| 亚洲欧美日韩综合aⅴ视频| 亚洲免费av片| 亚洲黄色影院| 在线看片日韩| 韩日精品在线| 国产主播一区二区三区| 国产精品日韩欧美大师| 欧美色图一区二区三区| 欧美日韩国产成人在线91| 狼人社综合社区| 久久久人成影片一区二区三区观看| 亚洲男女毛片无遮挡| 亚洲视频在线观看| 亚洲天堂av在线免费| 日韩视频一区二区三区在线播放免费观看| 免费成人黄色av| 美女精品自拍一二三四| 蜜桃av一区二区| 男人插女人欧美| 欧美91视频| 亚洲大胆美女视频| 久久久欧美一区二区| 午夜一区二区三区在线观看| 亚洲午夜久久久久久尤物| 中文无字幕一区二区三区| 在线亚洲欧美视频| 亚洲欧美春色| 欧美一区二区高清| 久久精品女人的天堂av| 久久九九国产| 欧美大片专区| 欧美日韩国产欧美日美国产精品| 欧美日韩精品久久| 国产精品午夜在线| 国产一区清纯| 亚洲黄色成人久久久| 亚洲另类在线一区| 午夜精品久久久久久久久久久久 | 亚洲欧美视频在线| 久久精品2019中文字幕| 免费在线看一区| 亚洲欧洲精品天堂一级| 亚洲一区二区三区中文字幕| 欧美一区二区成人| 欧美激情国产日韩| 国产精品久久久久久久久久直播| 国产丝袜一区二区| 亚洲欧洲精品一区二区三区不卡| 一本一道久久综合狠狠老精东影业 | 一区二区黄色| 久久不射2019中文字幕| 欧美国产精品中文字幕| av成人黄色| 久久久久成人精品免费播放动漫| 欧美黄在线观看| 国产午夜精品视频免费不卡69堂| 亚洲国产一区二区a毛片| 亚洲一区在线看| 欧美激情亚洲视频| 亚洲在线1234| 欧美另类videos死尸| 国产一区二区欧美日韩| 亚洲手机在线| 欧美成人国产| 午夜久久一区| 欧美理论视频| 在线免费一区三区| 欧美一区午夜精品| 夜夜嗨av一区二区三区免费区| 久久综合999| 国产一区二区三区四区在线观看 | 亚洲精品欧美精品|