S_nim-Sprague Grundy
update@2011-10-08
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出来了。