设L = left[i][j - 1], R = right[i][j - 1], X = a[j]. 通过下面的分析我们可以发现left[i][j]只和L, R, X三个数有关.
一大波情况分类:
当R = X时,left[i][j] = 0。
当X < L且X < R时, left[i][j] = X。
当R < x <= L时, left[i][j] = X - 1。
当L <= X < R时,left[i][j] = X + 1。
当x > L且x > R时,left[i][j] = X。
对于right[i][j]可做同样处理……
要是不看大神题解绝逼想不到这么神的做法……
orz Run Towards End:http://www.cnblogs.com/zcwwzdjn/archive/2012/05/26/2519685.html
#include<cstdio> #include<algorithm> using namespace std; int o,p; inline int read(){ p=0;o=getchar(); while(o<‘0‘||o>‘9‘) o=getchar(); while(o>=‘0‘&&o<=‘9‘) p=p*10+o-48,o=getchar(); return p; } int t,n,a[1000],l[1001][1001],r[1001][1001]; int main(){ register int i,j,k; t=read(); while(t--){ n=read(); for (i=0;i<n;i++) l[i][i]=r[i][i]=a[i]=read(); for (k=1;k<n-1;k++) for (i=0;i+k<n;i++){ j=i+k; if (a[j]==r[i][j-1]) l[i][j]=0;else if ((a[j]>l[i][j-1]&&a[j]>r[i][j-1])||(a[j]<l[i][j-1]&&a[j]<r[i][j-1])) l[i][j]=a[j];else if (l[i][j-1]<=a[j]&&r[i][j-1]>a[j]) l[i][j]=a[j]+1;else l[i][j]=a[j]-1; if (a[i]==l[i+1][j]) r[i][j]=0;else if ((a[i]>l[i+1][j]&&a[i]>r[i+1][j])||(a[i]<l[i+1][j]&&a[i]<r[i+1][j])) r[i][j]=a[i];else if (l[i+1][j]<=a[i]&&r[i+1][j]>a[i]) r[i][j]=a[i]+1;else r[i][j]=a[i]-1; } if (l[1][n-1]==a[0]) printf("0\n");else printf("1\n"); } }
vijos 1557:bzoj:1413: [ZJOI2009]取石子游戏
原文:http://www.cnblogs.com/Enceladus/p/5152417.html