Description 一个1~n的排列，每次可以拿走一个数当且仅当这个数大于其两边位置的数(0和n+1位置认为是0)，一个数被拿走之后可以认为这个位置的数是0，Alice和Bob轮流拿，谁拿走1谁赢，Alice先手，在双方足够机智的条件下问谁必胜 Input 第一行一整数T表示用例组数，每组用例首先输入一整数n，之后一个1~n的排列(1<=T<=100,1<=n<=100) Output 输出必胜者 Sample Input 4 4 2 1 3 4 4 1 3 2 4 3 1 3 2 6 2 5 1 6 4 3 Sample Output Bob Alice Bob Alice Solution 记dp[l][r][last]表示区间[l,r]被独立出来（即l-1和r+1位置都是0）且其他位置非零数剩下last个的必胜状态（1表示Alice必胜，0表示Bob必胜），那么答案就是dp[1][n][0]，而每种状态有两种后继状态，一是从[l,r]中拿走一个合法的数，二是从last个数中拿走一个（随便拿，不会影响[l,r]），如果所有后继都是必胜态则当前是必胜态，否则当前是必胜态，记忆化一下即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111 int T,n,pos,a[maxn],dp[maxn][maxn][maxn]; int dfs(int l,int r,int last) { if(dp[l][r][last]>=0)return dp[l][r][last]; if(l==r)return dp[l][r][last]=1; int ans=0; for(int i=l;i<=r;i++) { if(i==l&&a[l]>=a[l+1])ans|=dfs(l+1,r,last)^1; else if(i==r&&a[r]>=a[r-1])ans|=dfs(l,r-1,last)^1; else if(a[i]>=a[i-1]&&a[i]>=a[i+1]) { if(i>pos)ans|=dfs(l,i-1,last+r-i)^1; else ans|=dfs(i+1,r,last+i-l)^1; } } if(last)ans|=dfs(l,r,last-1)^1; return dp[l][r][last]=ans; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==1)pos=i; } memset(dp,-1,sizeof(dp)); printf("%s\n",dfs(1,n,0)?"Alice":"Bob"); } return 0; }