模板
bool flag=0;
while(h[i]<h[sta[top]])
top--,flag=1;
cr[sta[top]]=i;
if(flag)
cl[i]=sta[top+1];
sta[++top]=i;
受限制的排列
对于一个 1 到 n 的排列 p1, p2, ⋯, pn ，我们可以轻松地对于任意的 1 ≤ i ≤ n 计算出 (li, ri) ，使得对于任意的 1 ≤ L ≤ R ≤ n 来说 min(pL, pL + 1, ⋯, pR) = pi 当且仅当 li ≤ L ≤ i ≤ R ≤ ri 。
给定整数 n 和 (li, ri) (1 ≤ i ≤ n) ，你需要计算有多少种可能的 1 到 n 的排列 p1, p2, ⋯, pn 满足上述条件。
由于答案可能很大，你只需要给出答案对 109 + 7 取模的值。
题解
实际上它就是一个笛卡尔树，先找到一段区间的最值点，然后一分为二分别处理两边，此时最值定下来了，左右互不影响，因此有\(C_{len}^{l}\)种情况。用map记录很巧妙。
代码
#include<iostream>
#include<cstring>
using namespace std;
int t,n;
string s;
int dp[2005][2005];
int dfs(int l,int r){
if(dp[l][r]!=-1)
return dp[l][r];
if(l>r)
return dp[l][r]=1;
dp[l+2][r]=dfs(l+2,r);
dp[l][r-2]=dfs(l,r-2);
dp[l+1][r-1]=dfs(l+1,r-1);
if((s[l]==s[r]&&dp[l+1][r-1]==1)||(s[l]==s[l+1]&&dp[l+2][r]==1&&s[r]==s[r-1]&&dp[l][r-2]))
return dp[l][r]=1;
return dp[l][r]=0;
}
int main(){
scanf("%d\n",&t);
while(t--){
memset(dp,-1,sizeof(dp));
cin>>s;
n=s.size();
s=" "+s;
dfs(1,n);
if(dp[1][n]==1)
printf("Draw\n");
else
printf("Alice\n");
}
}