S_nim-Sprague Grundy

update@2011-10-08
C++语言: 高亮代码由发芽网提供

int S[110];
int heap[101][100];
int sg[10010];int k;
int minimum_excludant(int *temp,int count){
    sort(temp,temp+count);
    int v = 0;
    for(int i = 0;i < count;i++){
        if(temp[i] == v) v++;
    }
    return v;
}
void getSG(int maxx){
    for(int i = S[0]+1;i <= maxx;i++){
        int temp[10010],count = 0;
        for(int j = 0;j < k && S[j] <= i;j++){
            temp[count++] = sg[i - S[j]];//比i小的S[j]都可以作为操
        }
        sg[i] = minimum_excludant(temp,count);
    }
}


链接:S-nim
水题,理解了Sprague-Grundy的定义就能YY出来了。