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=='>')

代码：

CPP

#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;
}

AT_dp_t Permutation

文章操作

AT_dp_t Permutation

相关推荐

评论

AT_dp_t Permutation