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

coreBugZJ

此 blog 已棄。

POJ 2068 Nim

  1/*
  2POJ 2068 Nim
  3
  4
  5----問題描述:
  6
  7Let's play a traditional game Nim. You and I are seated across a table and we have a hundred stones on the table (we know the number of stones exactly). We play in turn and at each turn, you or I can remove on to four stones from the heap. You play first and the one who removed the last stone loses. 
  8
  9In this game, you have a winning strategy. To see this, you first remove four stones and leave 96 stones. No matter how I play, I will end up with leaving 92 - 95 stones. Then you will in turn leave 91 stones for me (verify this is always possible). This way, you can always leave 5k+1 stones for me and finally I get the last stone, sigh. If we initially had 101 stones, on the other hand, I have a winning strategy and you are doomed to lose. 
 10
 11Let's generalize the game a little bit. First, let's make it a team game. Each team has n players and the 2n players are seated around the table, with each player having opponents at both sides. Turn around the table so the two teams play alternately. Second, let's vary the maximum number of stones each player can take. That is, each player has his/her own maximum number of stones he/she can take at each turn (The minimum is always one). So the game is asymmetric and may even be unfair. 
 12
 13In general, when played between two teams of experts, the outcome of a game is completely determined by the initial number of stones and the maximum number of stones each player can take at each turn. In other words, either team has a winning strategy. 
 14
 15You are the head-coach of a team. In each game, the umpire shows both teams the initial number of stones and the maximum number of stones each player can take at each turn. Your team plays first. Your job is, given those numbers, to instantaneously judge whether your team has a winning strategy. 
 16
 17Incidentally, there is a rumor that Captain Future and her officers of Hakodate-maru love this game, and they are killing their time playing it during their missions. You wonder where the stones are? Well, they do not have stones but do have plenty of balls in the fuel containers!
 18
 19
 20----輸入:
 21
 22The input is a sequence of lines, followed by the last line containing a zero. Each line except the last is a sequence of integers and has the following format. 
 23
 24n S M1 M2 . . . M2n 
 25
 26where n is the number of players in a team, S the initial number of stones, and Mi the maximum number of stones ith player can take. 1st, 3rd, 5th,  players are your team's players and 2nd, 4th, 6th,  the opponents. Numbers are separated by a single space character. You may assume 1 <= n <= 10, 1 <= Mi <= 16, and 1 <= S < 2^13.
 27
 28
 29----輸出:
 30
 31The output should consist of lines each containing either a one, meaning your team has a winning strategy, or a zero otherwise.
 32
 33
 34----樣例輸入:
 35
 361 101 4 4
 371 100 4 4
 383 97 8 7 6 5 4 3
 390
 40
 41
 42----樣例輸出:
 43
 440
 451
 461
 47
 48
 49----分析:
 50
 51博弈DP ,記憶化搜索。
 52
 53
 54*/

 55
 56
 57#include <iostream>
 58#include <cstdio>
 59#include <cstring>
 60
 61using namespace std;
 62
 63const int N = 29;
 64
 65int n, s, m[ N ], f[ N ][ (1<<13+ 9 ];
 66
 67        // 到第 i 個人,面對 j 個石子,奇數方勝則為 1,敗則為 0 .
 68int dp( int i, int j ) {
 69        if ( -1 != f[ i ][ j ] ) {
 70                return f[ i ][ j ];
 71        }

 72
 73        if ( 0 == j ) {
 74                return ( f[ i ][ j ] = (i & 1) );
 75        }

 76
 77        int k;
 78        f[ i ][ j ] = 1 - (i & 1);
 79        for ( k = 1; (k <= j)&&(k <= m[ i ]); ++k ) {
 80                if ( (i & 1== dp( i%n+1, j - k ) ) {
 81                        f[ i ][ j ] = (i & 1);
 82                        break;
 83                }

 84        }

 85        return f[ i ][ j ];
 86}

 87
 88int main() {
 89        int i;
 90        while ( (1 == scanf( "%d"&n )) && (0 < n) ) {
 91                scanf( "%d"&s );
 92                n <<= 1;
 93                for ( i = 1; i <= n; ++i ) {
 94                        scanf( "%d", m+i );
 95                }

 96                memset( f, 0xFFsizeof(f) );
 97                printf( "%d\n", dp( 1, s ) );
 98        }

 99        return 0;
100}

101

posted on 2012-06-04 16:03 coreBugZJ 閱讀(897) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲香蕉网站| 国产精品九九| 精品88久久久久88久久久| 久久er99精品| 欧美呦呦网站| 亚洲电影免费观看高清| 亚洲国产成人精品女人久久久| 麻豆精品视频在线观看视频| 一本久道久久综合婷婷鲸鱼| 亚洲视频免费在线观看| 国产视频一区二区在线观看| 蜜臀av性久久久久蜜臀aⅴ| 久久久久九九九九| 99re66热这里只有精品3直播| aaa亚洲精品一二三区| 国产日韩一级二级三级| 亚洲高清在线观看| 国产精品免费网站在线观看| 久久深夜福利免费观看| 欧美精品在线看| 欧美在线免费播放| 欧美成人一区二区在线| 亚洲欧美文学| 裸体歌舞表演一区二区| 午夜欧美精品| 免费毛片一区二区三区久久久| 亚洲午夜在线| 免费成人黄色片| 欧美一区综合| 欧美日韩精品一本二本三本| 蜜臀99久久精品久久久久久软件 | 91久久一区二区| 国产日韩在线视频| 99国产精品99久久久久久粉嫩| 狠狠噜噜久久| 亚洲天堂av图片| 一区二区三区四区五区精品视频| 久久黄金**| 小嫩嫩精品导航| 午夜在线电影亚洲一区| 免费成人你懂的| 老牛国产精品一区的观看方式| 欧美日韩中文字幕| 91久久久久久| 亚洲欧洲三级电影| 久久久久久一区| 久久久精品免费视频| 国产精品久久波多野结衣| 亚洲精品在线一区二区| 亚洲开发第一视频在线播放| 狂野欧美一区| 美女日韩欧美| 亚洲国产高清自拍| 久热综合在线亚洲精品| 久久久青草婷婷精品综合日韩| 国产精品任我爽爆在线播放| 99ri日韩精品视频| 国产精品99久久久久久久久| 欧美成人一区二免费视频软件| 欧美成人精品福利| 亚洲福利视频三区| 欧美1区3d| 亚洲福利视频专区| 亚洲精品在线观| 欧美日韩1080p| 一级成人国产| 亚洲欧美日韩视频二区| 国产精品萝li| 亚洲欧美日韩在线高清直播| 午夜日韩电影| 国内精品亚洲| 美女视频网站黄色亚洲| 91久久精品美女| 亚洲视频二区| 国产精品久久影院| 久久国产乱子精品免费女 | 亚洲精品国久久99热| 欧美日韩成人| 亚洲欧美资源在线| 久久一区亚洲| 亚洲人人精品| 欧美视频精品在线| 欧美亚洲色图校园春色| 美日韩精品视频| 一区二区三区成人| 国产精品亚发布| 蜜桃久久精品乱码一区二区| 亚洲激情影视| 欧美在线播放一区| 亚洲国产精品一区制服丝袜| 欧美福利视频一区| 亚洲视频一二区| 久久精品国产91精品亚洲| 亚洲黑丝在线| 国产欧美精品日韩精品| 蜜臀va亚洲va欧美va天堂 | 亚洲大胆女人| 午夜视频在线观看一区| 精品电影一区| 欧美日韩在线一区二区三区| 久久精品一本| 一区二区日韩欧美| 欧美91福利在线观看| 亚洲综合国产| 亚洲精品欧美日韩| 国产亚洲一区精品| 欧美日韩视频第一区| 久久乐国产精品| 亚洲综合欧美| 99精品欧美一区| 欧美大片18| 久久久久国产免费免费| 亚洲欧美另类中文字幕| 亚洲激情第一页| 国内久久精品视频| 国产九色精品成人porny| 欧美激情视频给我| 另类激情亚洲| 久久精品电影| 性久久久久久久| 亚洲免费在线视频一区 二区| 亚洲日本aⅴ片在线观看香蕉| 久久久国产午夜精品| 亚洲欧美一区二区精品久久久| 亚洲精品国产精品乱码不99| 黄色综合网站| 激情六月婷婷久久| 国产一区二区久久| 国产区亚洲区欧美区| 国产精品成人播放| 欧美日韩综合不卡| 性欧美xxxx大乳国产app| 亚洲午夜精品17c| 一区二区三区四区国产精品| 999亚洲国产精| 亚洲精品网址在线观看| 亚洲人成网站色ww在线 | 欧美日本在线一区| 欧美—级高清免费播放| 欧美电影免费观看高清完整版| 老司机午夜精品视频在线观看| 狂野欧美激情性xxxx欧美| 美女脱光内衣内裤视频久久网站| 久久久精品一区二区三区| 久久电影一区| 久久躁日日躁aaaaxxxx| 久久一区二区三区国产精品 | 欧美一区在线视频| 久久久久久久欧美精品| 麻豆av福利av久久av| 欧美成人福利视频| 欧美人妖另类| 国产精品乱子久久久久| 国产一区二区日韩| 激情校园亚洲| 99国产精品久久久久久久成人热| 一区二区日韩欧美| 欧美中文字幕在线| 蜜桃精品久久久久久久免费影院| 亚洲福利电影| 亚洲午夜激情免费视频| 久久国产精彩视频| 欧美国产日本高清在线| 久久精品论坛| 亚洲国产精品成人va在线观看| 亚洲精品看片| 午夜欧美精品| 免费不卡欧美自拍视频| 国产精品进线69影院| 在线成人免费视频| 日韩一二在线观看| 久久激情视频| 91久久精品国产91性色| 亚洲欧美视频一区二区三区| 久久中文欧美| 国产精品xnxxcom| 亚洲黄色av一区| 欧美一区亚洲| 亚洲精品美女在线| 久久久久高清| 欧美午夜精品久久久| 在线观看国产精品淫| 亚洲免费视频一区二区| 免费日韩av电影| 亚洲伊人观看| 欧美日韩精品免费看 | 欧美日韩免费区域视频在线观看| 国产一区二区你懂的| 中文欧美在线视频| 欧美国产精品v| 欧美一区二区三区视频在线 | 国产精品超碰97尤物18| 亚洲国产精品精华液网站| 欧美一区二区三区久久精品茉莉花| 亚洲第一天堂av| 老鸭窝91久久精品色噜噜导演| 国产日本欧美一区二区三区| 亚洲一卡久久| 99re6热在线精品视频播放速度| 久久欧美中文字幕|