poj3537 Crosses and Crosses----sg

Crosses and Crosses
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 1866   Accepted: 687
Case Time Limit: 2000MS
Description
The game of Crosses and Crosses is played on the field of 1 × n cells. Two players make moves in turn. Each move the player selects any free cell on the field and puts a cross ‘×’ to it. If after the player’s move there are three crosses in a row, he wins.
You are given n. Find out who wins if both players play optimally.
Input
Input file contains one integer number n (3 ≤ n ≤ 2000).
Output
Output ‘1’ if the first player wins, or ‘2’ if the second player does.
Sample Input
#1 3
#2 6
Sample Output
#1 1
#2 2
Source
Northeastern Europe 2007, Northern Subregion
 
在第I個位置放一個X，即可分為兩個子游戲，I-3和n-I-2
 
[cpp] 
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
#include<memory.h> 
using namespace std; 
int sg[2100]; 
int dfs(int n) 
{ 
    if(n<0) return 0;//n<0 
    if(sg[n]>=0) return sg[n]; 
    bool g[2001]={0}; 
    for(int i=1;i<=n;i++) 
    { 
        int t=dfs(i-3)^dfs(n-i-2); 
        g[t]=1; 
    } 
    for(int i=0;;i++) 
    if(g[i]==0) return sg[n]=i; 
} 
int main() 
{ 
    memset(sg,-1,sizeof(sg)); 
    int n; 
    while(scanf("%d",&n)!=EOF) 
    { 
        if(dfs(n)) puts("1"); 
        else puts("2"); 
    } 
}