bzoj1413 取石子遊戲 遞推

       自古浙江出神題。。然後資料還很弱。。

       參考了這裡的思路。可以發現對于任意一段[i,j]，在其左邊添上一個數，隻有唯一的一個數（包括0即不添加）能夠使新的序列[i-1,j]是一個必敗狀态。顯然，如果有兩個x,y都滿足，不妨設x<y，那麼對于y+[i,j]這個狀态，可以把y取到x使其成為必敗狀态，這與每一個必敗狀态都轉移不到必敗狀态沖突。故得證。可知在右邊添上一個數同理。

       令l[i][j]表示[i,j]左邊添上的數，r[i][j]表示右邊添上的數。假設我們已經知道了x=l[i-1][j],y=r[i][j-1],z=a[j]，那麼：

       1.特殊情況a[j]=y，那麼[i,j]本身就是一個必敗狀态，l[i][j]=0；

       2.如果a[j]<x,y，那麼令l[i][j]=a[j]，然後先手在一邊取k個，後手就在另一邊取k個。新手顯然先取到了，那麼此時還剩下的那一堆的數量顯然<x,y，是以後手有必勝政策；

       3.考慮x<=a[j]<y，那麼令l[i][j]=a[j]+1，然後在第j堆個數>=x時，後手始終保持讓第i-1堆得比第j堆得多一個；當第j堆個數<x時，後手始終保持第i-1堆和第j堆相同，然後同2；

       4.考慮y<a[j]<=x，那麼令l[i][j]=a[j]-1，然後同3；

       5.考慮a[j]>x,y，那麼令l[i][j]=a[j]。不妨設x<y（x>y同理），那麼當第i-1堆個數>y時，後手保持第i-1堆和第j堆相同；然後同3；

       最後，如果a[1]==l[2][n]則無解；反之有解。

AC代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1005
using namespace std;

int n,a[N],l[N][N],r[N][N];
int main(){
	int cas; scanf("%d",&cas);
	while (cas--){
		scanf("%d",&n); int i,j;
		for (i=1; i<=n; i++) scanf("%d",&a[i]);
		for (i=1; i<=n; i++) l[i][i]=r[i][i]=a[i];
		for (i=n-1; i; i--) for (j=i+1; j<=n; j++){
			int x=l[i][j-1],y=r[i][j-1],z=a[j];
			if (z==y) l[i][j]=0; else
				if (z<x && z<y || z>x && z>y) l[i][j]=z; else
					if (x>y) l[i][j]=z-1; else l[i][j]=z+1;
			x=r[i+1][j]; y=l[i+1][j]; z=a[i];
			if (z==y) r[i][j]=0; else
				if (z<x && z<y || z>x && z>y) r[i][j]=z; else
					if (x>y) r[i][j]=z-1; else r[i][j]=z+1;
		}
		if (n==1) puts("1"); else printf("%d\n",(a[1]==l[2][n])?0:1);
	}
	return 0;
}
           

by lych 2016.2.24