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

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>
            激情综合色丁香一区二区| 欧美日韩成人在线观看| 国产亚洲激情视频在线| 久久成人精品无人区| 欧美一区二区三区四区视频 | 亚洲一区观看| 国产一区二区三区不卡在线观看| 久久久精品一品道一区| 久久亚洲一区二区| 一区二区三区欧美日韩| 亚洲欧美成人网| 亚洲大胆人体视频| 一区二区三区高清在线| 国产一区二区高清不卡| 亚洲国产99精品国自产| 嫩草伊人久久精品少妇av杨幂| 亚洲私人影院在线观看| 久久国产精品久久久久久| 亚洲美女精品成人在线视频| 亚洲一二三区在线| 影院欧美亚洲| 亚洲一区二区三区乱码aⅴ蜜桃女| 激情国产一区| aa级大片欧美三级| 一区二区在线视频观看| 一区二区三区日韩欧美| 1024国产精品| 亚洲午夜一二三区视频| 亚洲国产影院| 亚洲欧美日韩一区在线| 亚洲青涩在线| 久久精品视频在线观看| 亚洲在线第一页| 欧美va亚洲va国产综合| 久久成人免费网| 欧美日韩一本到| 欧美黑人一区二区三区| 国产一区二区三区在线播放免费观看| 亚洲国产日韩欧美在线图片| 欧美大色视频| 国产情人节一区| 日韩视频在线一区二区| 亚洲日本免费电影| 久久久美女艺术照精彩视频福利播放 | 欧美男人的天堂| 欧美大片在线观看一区二区| 国产亚洲精品久久飘花| 亚洲一区二区三区久久 | 在线日韩av永久免费观看| 午夜在线电影亚洲一区| 亚洲影视中文字幕| 麻豆国产精品va在线观看不卡| 久久国产视频网站| 国产精品亚洲一区| 中文av一区特黄| 亚洲一区二区三区高清不卡| 欧美日韩国产小视频| 亚洲三级电影在线观看| 亚洲精品视频在线播放| 免费黄网站欧美| 欧美激情视频在线播放| 亚洲福利视频网| 免费高清在线一区| 欧美激情一区二区三区不卡| 亚洲欧洲精品一区二区三区 | 久久久久青草大香线综合精品| 久久福利视频导航| 国产在线精品自拍| 欧美在线视频免费| 久久综合五月| 亚洲国产精品久久久久秋霞不卡 | 99精品视频一区| 亚洲私人影院在线观看| 国产精品嫩草影院一区二区 | 国产精品国产三级国产普通话三级 | 亚洲午夜精品福利| 国产精品久久久久久久久婷婷| 一区二区三区高清在线| 久久国产88| 亚洲韩国日本中文字幕| 欧美激情视频给我| 亚洲天堂黄色| 乱人伦精品视频在线观看| 亚洲人成7777| 欧美色中文字幕| 欧美亚洲一区在线| 欧美激情一二三区| 亚洲综合国产激情另类一区| 国产一区三区三区| 男男成人高潮片免费网站| 亚洲精品视频在线观看网站| 午夜日本精品| 亚洲国产精品高清久久久| 欧美日韩一区二区三区在线| 亚洲欧美电影院| 欧美激情按摩| 先锋影音久久久| 亚洲日本成人在线观看| 国产精品午夜av在线| 久久在线观看视频| 亚洲一区二区三区国产| 欧美黄色免费网站| 久久本道综合色狠狠五月| 最近中文字幕日韩精品| 国产精品一区在线观看你懂的| 久久久综合网站| 国产精品99久久久久久宅男| 免费不卡亚洲欧美| 香蕉乱码成人久久天堂爱免费 | 国产精品有限公司| 欧美精品激情在线| 久久精品女人| 亚洲专区在线| 亚洲老司机av| 欧美激情1区| 久久久久九九视频| 亚洲男人天堂2024| 99国产精品国产精品久久| 黄色国产精品一区二区三区| 国产精品福利网站| 欧美精品在线免费| 欧美成年人网站| 久久精品国产视频| 亚洲女优在线| 亚洲婷婷综合久久一本伊一区| 亚洲国产天堂久久综合| 美日韩精品视频| 久久久久久久国产| 久久av一区| 欧美中日韩免费视频| 午夜国产欧美理论在线播放| 亚洲午夜激情网站| 一区二区三区国产| 艳妇臀荡乳欲伦亚洲一区| 亚洲东热激情| 最新国产の精品合集bt伙计| 在线观看日韩av先锋影音电影院 | 欧美日本国产精品| 欧美了一区在线观看| 欧美韩日一区| 欧美日本高清视频| 欧美成人dvd在线视频| 久久国产一二区| 久久久国产亚洲精品| 欧美在现视频| 久久久中精品2020中文| 毛片av中文字幕一区二区| 麻豆91精品| 欧美激情一区二区三区在线视频观看 | 日韩视频免费看| 99热在这里有精品免费| 亚洲天堂激情| 欧美呦呦网站| 欧美 日韩 国产精品免费观看| 欧美成人精品高清在线播放| 欧美日韩国产一区二区三区| 欧美成人激情在线| 欧美日精品一区视频| 国产乱码精品1区2区3区| 国内成人精品一区| 最新精品在线| 亚洲一区二区毛片| 久久精品成人| 久久久久国内| 亚洲精品国产精品国自产观看浪潮 | 免费亚洲电影在线观看| 欧美伦理91i| 国产精品一区免费视频| 在线观看欧美亚洲| 亚洲一区久久久| 久久久久久久久久久久久9999| 欧美成人视屏| 亚洲视频在线一区观看| 久久亚洲欧美| 欧美性jizz18性欧美| 激情久久久久久| 在线一区视频| 欧美日韩视频一区二区三区| 国产亚洲欧洲一区高清在线观看| 91久久综合| 久久激情视频| 日韩午夜电影| 久久只有精品| 国产精品影视天天线| 一本一本久久a久久精品综合麻豆| 欧美专区日韩专区| 亚洲麻豆视频| 久久影院午夜片一区| 国产女主播一区二区| 日韩视频第一页| 噜噜噜躁狠狠躁狠狠精品视频| 一本一本大道香蕉久在线精品| 久久久久久久久久久久久女国产乱| 欧美三级欧美一级| 亚洲精品一区在线观看| 久久色在线播放| 亚洲欧美成aⅴ人在线观看| 欧美日韩精品二区| 最新国产の精品合集bt伙计| 久热成人在线视频|