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

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 閱讀(904) 評論(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>
            久久大逼视频| 亚洲精品在线三区| 亚洲免费观看高清完整版在线观看熊 | 久久久欧美一区二区| 欧美乱人伦中文字幕在线| 老**午夜毛片一区二区三区| 国产精品国产亚洲精品看不卡15| 亚洲成色777777在线观看影院| 国产欧美亚洲一区| 国产精品99久久久久久白浆小说 | 久久国内精品视频| 欧美午夜国产| 日韩午夜在线电影| 日韩亚洲视频| 欧美激情视频在线播放 | 在线观看一区欧美| 性娇小13――14欧美| 亚洲欧美日韩在线一区| 欧美区高清在线| 91久久线看在观草草青青| 一区视频在线看| 久久久成人网| 老司机精品视频网站| 国产一区二区三区直播精品电影| 亚洲欧美视频在线观看视频| 亚洲欧美一区二区三区极速播放| 欧美区在线播放| 日韩网站在线看片你懂的| 一区二区三区精品视频在线观看| 欧美乱妇高清无乱码| 亚洲第一页中文字幕| 亚洲精品国产拍免费91在线| 欧美精品免费在线观看| 亚洲精品系列| 亚洲欧美成人一区二区在线电影| 国产精品第十页| 亚洲免费在线播放| 欧美综合二区| 在线日韩av| 欧美精品一二三| 一区二区不卡在线视频 午夜欧美不卡在 | 久久久久九九视频| 在线观看精品视频| 欧美成人网在线| 99精品国产在热久久下载| 亚洲一区精品在线| 国产一区二区日韩| 免费成人你懂的| 一区二区三区高清不卡| 性亚洲最疯狂xxxx高清| 韩国免费一区| 欧美第一黄色网| 亚洲午夜久久久久久久久电影院 | 夜夜嗨av一区二区三区网站四季av | 午夜精品999| 蘑菇福利视频一区播放| 欧美专区第一页| 国产精品久线观看视频| 亚洲人成在线播放| 亚洲国产欧美一区二区三区久久| 性亚洲最疯狂xxxx高清| 午夜精品三级视频福利| 欧美日韩三级在线| 亚洲日本欧美| 一区二区电影免费观看| 欧美精品啪啪| 亚洲美女性视频| 中文亚洲免费| 国产精品第一区| 亚洲一区图片| 欧美一区二区三区在线播放| 国产乱码精品一区二区三| 亚洲一级在线观看| 欧美专区日韩专区| 国产亚洲一级高清| 久久久久久自在自线| 母乳一区在线观看| 亚洲欧洲一二三| 欧美日韩精品在线播放| 99精品热视频只有精品10| 亚洲一区在线免费| 国产毛片一区| 久久亚洲不卡| 亚洲日产国产精品| 亚洲欧美日韩成人| 国内激情久久| 欧美激情一区二区在线 | 久久久久欧美| 亚洲人成艺术| 国产精品爱久久久久久久| 亚洲无限av看| 免费试看一区| 中国成人在线视频| 国产午夜精品视频| 欧美jjzz| 午夜精品久久久久久99热| 免费毛片一区二区三区久久久| 亚洲精品日韩在线| 国产精品视频1区| 巨乳诱惑日韩免费av| 999亚洲国产精| 久久中文字幕一区| av成人老司机| 国产一区二区三区日韩| 美女视频黄免费的久久| 亚洲视频在线观看三级| 男人插女人欧美| 亚洲欧美成人在线| 亚洲国产一区二区三区a毛片| 欧美日韩亚洲国产精品| 欧美呦呦网站| 亚洲靠逼com| 久久这里有精品15一区二区三区| 一本大道久久a久久精二百| 国产综合第一页| 国产精品福利在线观看网址| 麻豆av一区二区三区久久| 在线视频欧美日韩精品| 亚洲大胆人体视频| 久久精品国亚洲| 亚洲欧美综合网| 中文精品一区二区三区| 亚洲国产一区在线观看| 国产亚洲欧美激情| 国产精品久久久久久模特| 欧美国产极速在线| 久久天天狠狠| 久久精品综合网| 午夜精品美女自拍福到在线 | 欧美激情91| 久久天堂成人| 久久国产精品久久久久久| 一本综合精品| 亚洲伦理在线| 亚洲精品欧美一区二区三区| 激情婷婷亚洲| 今天的高清视频免费播放成人| 国产精品视频999| 国产精品理论片| 国产精品久久精品日日| 欧美视频在线观看 亚洲欧| 欧美精品成人一区二区在线观看| 美女精品在线观看| 免费观看成人| 欧美精品成人| 欧美日产一区二区三区在线观看| 免费在线观看精品| 美女脱光内衣内裤视频久久网站| 久久婷婷国产麻豆91天堂| 久久精品国产精品亚洲精品| 欧美在线视频a| 久久视频一区| 欧美成人精品激情在线观看| 欧美激情第三页| 欧美日韩国产在线观看| 欧美色道久久88综合亚洲精品| 欧美午夜免费影院| 国产精品男女猛烈高潮激情| 国产欧美一区二区色老头| 国产亚洲精品自拍| 雨宫琴音一区二区在线| 亚洲韩日在线| 亚洲五月六月| 久久久精品免费视频| 美女主播视频一区| 亚洲国产女人aaa毛片在线| 亚洲精品偷拍| 午夜视频在线观看一区二区三区 | 午夜精品在线观看| 久久国产精品亚洲77777| 裸体歌舞表演一区二区| 欧美久久久久久久| 国产精品日韩在线| 在线成人av| 亚洲综合精品一区二区| 久久婷婷国产综合国色天香| 亚洲国产高清一区二区三区| 一区二区三区国产盗摄| 欧美在线播放高清精品| 欧美精品国产精品日韩精品| 国产精品久久久久久久午夜 | 一区二区三区在线免费播放| 亚洲美女在线视频| 性欧美1819性猛交| 亚洲第一网站免费视频| 亚洲一区3d动漫同人无遮挡| 久久―日本道色综合久久| 欧美日韩精品一区二区| 精品电影一区| 亚洲欧美日韩爽爽影院| 亚洲电影免费观看高清| 亚洲午夜精品| 欧美精品自拍偷拍动漫精品| 国产亚洲一本大道中文在线| 一区二区三区免费网站| 欧美aa国产视频| 欧美诱惑福利视频| 欧美午夜影院| 亚洲美女在线看| 欧美暴力喷水在线|