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

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>
            一本色道综合亚洲| 欧美视频在线观看免费网址| 亚洲天堂网在线观看| 久久人人看视频| 久久福利资源站| 国产精品福利av| 亚洲日本aⅴ片在线观看香蕉| 狠狠色狠狠色综合日日tαg | 日韩一区二区精品葵司在线| 亚洲福利在线看| 欧美在线观看网站| 欧美在线播放| 国产精品一区二区在线观看| a4yy欧美一区二区三区| 中日韩男男gay无套| 欧美日本簧片| 日韩网站在线观看| 亚洲一区二区三区中文字幕在线 | 亚洲黄色成人| 日韩视频亚洲视频| 欧美理论片在线观看| 亚洲国产成人av| 99国产精品自拍| 欧美三级午夜理伦三级中视频| 亚洲美女精品一区| 中文精品视频一区二区在线观看| 欧美日韩综合| 亚洲免费在线观看| 久久久久久久久蜜桃| 伊人狠狠色丁香综合尤物| 两个人的视频www国产精品| 欧美a级在线| 99视频超级精品| 国产精品高潮久久| 久久精品人人做人人爽| 欧美激情精品久久久久久黑人 | 欧美—级在线免费片| 日韩午夜视频在线观看| 亚洲欧美一区二区精品久久久| 国产精品香蕉在线观看| 久久九九精品| 最新日韩在线视频| 亚欧成人精品| 亚洲福利视频免费观看| 欧美日韩一区三区| 久久爱www.| 亚洲人体影院| 久久精品国语| 99国产精品一区| 国产日韩欧美二区| 欧美成人一区二区三区片免费| 夜夜嗨av色一区二区不卡| 久久爱www.| 亚洲另类在线一区| 国产日韩欧美91| 欧美精品在线观看| 久久aⅴ乱码一区二区三区| 亚洲激情黄色| 久久精品国产一区二区三区免费看 | 99精品视频免费观看| 国产欧美一区二区色老头| 免费观看在线综合色| 国产精品爽黄69| 嫩草成人www欧美| 亚洲一区二区视频| 91久久中文| 久久久久久自在自线| 亚洲午夜一级| 亚洲日本成人网| 国产日韩欧美在线播放不卡| 欧美日本亚洲视频| 久久亚洲私人国产精品va媚药| 亚洲午夜在线观看视频在线| 91久久视频| 蜜臀av性久久久久蜜臀aⅴ四虎| 亚洲欧美在线观看| 中文在线资源观看网站视频免费不卡| 国产一区二区三区直播精品电影| 欧美日韩免费在线观看| 蜜臀91精品一区二区三区| 欧美一级黄色网| 亚洲一品av免费观看| 亚洲三级视频在线观看| 亚洲第一级黄色片| 欧美不卡三区| 欧美www视频在线观看| 久久精品综合网| 欧美一区二区在线| 午夜在线视频一区二区区别 | 日韩视频―中文字幕| 亚洲福利视频一区二区| 在线成人亚洲| 在线观看欧美激情| 精品999成人| 国内外成人免费激情在线视频网站| 国产乱码精品1区2区3区| 国产精品久久久久影院色老大 | 黄色精品一区二区| 国内成人在线| 黑人巨大精品欧美黑白配亚洲| 国产视频久久久久久久| 国产日韩欧美电影在线观看| 国产乱码精品一区二区三区不卡| 国产精品国产成人国产三级| 国产精品chinese| 国产精品久久9| 国产精品婷婷| 国产亚洲欧美一区| 伊人狠狠色丁香综合尤物| 一区二区视频免费完整版观看| 狠狠色伊人亚洲综合成人| 黄色日韩在线| 亚洲高清中文字幕| 99精品国产高清一区二区 | 一区二区三区四区国产精品| 一区二区三区欧美视频| 亚洲一区二区在线播放| 欧美一区二区三区免费观看| 久久久福利视频| 欧美成人日韩| 99成人免费视频| 亚洲影音一区| 久久久xxx| 欧美精品免费看| 国产精品久久久久久久久免费桃花| 欧美午夜精品电影| 国产主播精品在线| 亚洲人成在线影院| 亚洲一区在线直播| 久久野战av| 亚洲精品欧美| 亚洲一区二区影院| 99在线热播精品免费99热| 欧美一区二区三区免费在线看| 狼狼综合久久久久综合网 | 午夜视频精品| 欧美国产激情| 国产亚洲成精品久久| 亚洲国产天堂网精品网站| 亚洲在线中文字幕| 免费日韩精品中文字幕视频在线| 亚洲毛片在线免费观看| 欧美在线观看一区二区| 欧美日韩国产成人在线免费| 国产日韩亚洲欧美综合| 夜久久久久久| 毛片精品免费在线观看| 亚洲少妇在线| 欧美www视频| 狠狠入ady亚洲精品| 亚洲网站在线看| 欧美激情一区二区三级高清视频| 亚洲网站在线看| 欧美凹凸一区二区三区视频| 国产欧美一区二区三区在线老狼| 艳妇臀荡乳欲伦亚洲一区| 久久综合精品一区| 午夜精品av| 国产精品h在线观看| 亚洲狼人综合| 欧美风情在线| 久久久99国产精品免费| 国产欧美精品一区aⅴ影院| 日韩小视频在线观看专区| 蜜桃av噜噜一区| 久久aⅴ国产紧身牛仔裤| 国产精品视频网| 亚洲素人在线| 日韩视频精品在线观看| 欧美成人精品激情在线观看| 尤妮丝一区二区裸体视频| 久久本道综合色狠狠五月| 亚洲视频高清| 国产精品播放| 亚洲免费影视| 一本一本a久久| 欧美色欧美亚洲另类七区| 一本久久综合亚洲鲁鲁五月天| 欧美激情91| 免费美女久久99| 亚洲激情专区| 亚洲国产精品va| 欧美大片一区| 日韩视频专区| 99国产精品国产精品毛片| 欧美片网站免费| 亚洲视频一二三| 一级日韩一区在线观看| 国产精品va| 香蕉久久精品日日躁夜夜躁| 亚洲天堂免费观看| 国产精品一区二区在线观看不卡| 欧美一区二区三区婷婷月色| 亚洲欧美日韩电影| 国内精品久久久久伊人av| 久久久在线视频| 老鸭窝91久久精品色噜噜导演| 91久久久久久久久| 亚洲免费av片| 国产精品亚洲а∨天堂免在线|