uva10404

2560 단어
제목 대의: 돌의 총수와 m더미의 수량을 제시하고, 매번 m더미의 수량 중 한 무더기를 얻을 수 있다.마지막에 누가 이길지 제발.
사고방식: dp[i]로 남은 i개의 돌멩이stan이 이길 수 있는지를 표시하고, 1은 이길 수 있는지, 0은 이길 수 없는지를 표시한다.i>=f[j]일 때, 그리고 dp[i-f[j]==0일 때stan이 이길 것이다. 선자가 이기고 후자가 진다고 가정하자.그러면 돌이 i-f[j]를 남겼을 때stan은 후자였고, 돌이 i였을 때stan은 선자가 되었기 때문에 이럴 때stan이 이길 것이다.
코드:
#include <iostream>
using namespace std;
#include <stdio.h>
#include <cstring>

int f[15];
int dp[1000006];
int main() {
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF) {
        //scanf("%d",&m);
    // printf("%d %d",n,m);
        for(int i = 0; i < m ; i++)
            scanf("%d",&f[i]);
        dp[0] = 0;
        for(int i = 1; i <= n ; i++) {
            dp[i] = 0;
            for(int j = 0; j < m ; j++) {
                if(i >= f[j] && !dp[i - f[j]]) {
                    dp[i] = 1;
                    break;
                }
            }
        }
        if(dp[n])
            printf("Stan wins
"
); else printf("Ollie wins
"
); } return 0; }

좋은 웹페이지 즐겨찾기