題目鏈接：https://loj.ac/problem/10248#submit_code
解題思路
神仙題目，迷一般的狀態轉移，看了yyb大佬的題解，才算明白一點，我們定義L[i][j]表示區間[i,j]左邊(即i-1位)加上一堆石子L[i][j]，能使先手必敗，R[i][j]表示區間[i,j]右邊(即j+1位)加上一堆石子R[i][j]，能使先手必敗，首先，邊界L[i][i]，R[i][i]肯定是a[i] (Nim博弈)，然后最后只要判斷a[1]是否等于L[2][n]就能判斷先手必勝還是必敗了，
再看狀態轉移，L[i][j]由L[i][j-1]與R[i][j-1]轉移過來，R[i][j]由R[i+1][j]，L[i+1][j]轉移過來，先看L[i][j]，我們設L=L[i][j-1]，R[i][j-1]，x=a[j]，
- R=x，L[i][j]=0，因為此時已經是必敗態了，不必再添了，
- x<L&&x<R，L[i][j]=x，此時兩側石子一致，無論先手怎么去，后手只要模仿先手在另一側取相同的數量，這樣就能保證先手先取完，此時左側或右側肯定有一堆沒取完，此時可以等價的認為，當前是先手從L或R取了一定數量的石子轉移過來的，此時無論后手怎么取都是必勝的，
- L<x<R，L[i][j]=x+1，若先手在左側取，剩下石子為rest，rest=0，等價于先手在R的狀態下，在右側取了一定數量的石子轉移過來，rest<L，后手只要將右側石頭取到與rest相同，就可以轉移到第2種情況，rest=L，后手將右側石子取完，就轉移到L，rest>L，后手只要將右手石子取到rest-1即又回到當前情況，若先手在右側取，當rest=0，將左側取出L，即可轉移到L，當rest<L，同上，取左側，可以轉移到第2種情況，rest>=L，后手通過在左側或右側，使得左側=右側+1，又回到當前情況，
- R<x<L，L[i][j]=x-1，與第三種情況類似，可以看成互換一下左右兩側，
- 當x>L&&x>R，L[i][j]=x，無論先手怎么取，后手都可以轉移到之前和當前的狀態，
R[i][j]和L[i][j]是對稱的，類似的求解即可，
AC代碼
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e3+5;
int a[maxn],L[maxn][maxn],R[maxn][maxn];
int T,n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
L[i][i]=R[i][i]=a[i];
for(int len=2;len<=n;++len)
for(int i=1,j=i+len-1;j<=n;++i,++j)
{
int x=a[j],l=L[i][j-1],r=R[i][j-1];
if(x==r)
L[i][j]=0;
else
if((x>l&&x>r)||(x<l&&x<r))
L[i][j]=x;
else
if(r<x&&x<l)
L[i][j]=x-1;
else
L[i][j]=x+1;
x=a[i],l=L[i+1][j],r=R[i+1][j];
if(x==1)
R[i][j]=0;
else
if((x>l&&x>r)||(x<l&&x<r))
R[i][j]=x;
else
if(r<x&&x<l)
R[i][j]=x+1;
else
R[i][j]=x-1;
}
puts(a[1]==L[2][n]?"0":"1");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1477.html
標籤：區塊鏈
上一篇：零知識證明初見
下一篇：PTA 狼人殺-簡單版（c++）