AT_dp_t Permutation

yokai_ing · 2025-03-21 22:27:20 · 题解

AT_dp_t Permutation

考场上想的时候总想着分成一段一段处理（因为分来的一堆数排列方式一定），结果完全转移不了，果然我的dp跟石一样.

参考了机房另一位大佬的思路，他是一开始不考虑排列的情况，发现转移需记录当前位置的值，和能转移过来的状态，且只关心相对大小关系。

在知道这些后，就要开始根据排列的性质写转移。为防止同一个数被用两次，就按顺序依次加入每个数，枚举到第i个位置就加入i这个数，这样解决了重复问题。

然后按题目要求由每个位置是~< or >~分类讨论

对于f_{i,i}的转移很明显，在>时为0，<时为\sum\limits_{j=1}^{i-1}f_{i-1,j}。

但对于其他已经在之前出现过的数，要统计它在此位置的贡献，好像会出现重复，且不知道i往哪放，咋办？

其实因为它只关心相对大小，所以相当于把i加进去再把此时转移的j踢出来，做个离散化。这时你会发现，新的数列的方案还是和之前1到i-1在i-1个位置排的方案数一样，但数不同，所以算两个不同方案。 所以放行大胆地转移，这并不会重复。

注意：当>号时要加的是f_{i-1,j}，因为在此刻我们把j作为第i位时，上一个作结尾的j它就变成j+1了，是符合我们的转移条件的。

至于要计算1到j-1或j到n的前缀和，f_{i,j}能从f_{i,j-1}直接拿过来再加上当前位置需要多加上的就可以了。

f_{i,j}=f_{i-1,j-1}+f_{i,j-1}~~(s_i=='<')

f_{i,j}=f_{i-1,j}+f_{i,j+1}~~(s_i=='>')

代码：


#include<bits/stdc++.h>
using namespace std;
#define MAXN 3010
const int MOD=1e9+7;
int n,f[MAXN][MAXN];
char s[MAXN];
int main(){
    cin>>n>>(s+2);
    f[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]=='<'){
            for(int j=1;j<=i;j++)
                f[i][j]=(f[i-1][j-1]+f[i][j-1])%MOD;
        }else
            for(int j=i;j>=1;j--)
                f[i][j]=(f[i-1][j]+f[i][j+1])%MOD;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+f[n][i])%MOD;
    printf("%d\n",ans);
    return 0;
}