AT题解——AT4541 Permutation

· · 题解

题目传送门

属于比较典型的排列 dp，看到数据范围可以 O(n^2) 做，第一维定然是考虑到第 i 个位置。

发现如果将第二维设置成具体的数，不能保证这是一个排列，发现我们只关心相对大小关系，可以设置为排名。

即令 dp_{i,j} 表示考虑到前 i 个位置且第 i 个数目前的排名为 j 的方案数（排名是从小到大），分类讨论得出转移方程。

对于 < 的情况，第 i-1 个数原先的排名一定低于 j，于是有：

dp_{i,j}=\sum_{k=1}^{j-1} dp_{i-1,k}

同理，对于 > 的情况，第 i-1 个数原先的排名一定不高于 j，原因是加入一个比 i-1 上小的数，其排名上升了，于是有：

dp_{i,j}=\sum_{k=j}^{i-1} dp_{i-1,k}

这样复杂度是 O(n^3) 的，不难想到前缀和优化，可以降到 O(n^2)

代码

int n;
char s[3005];
int dp[3005][3005];
int sum[3005];
int main(){
    n=read();
    scanf("%s",s+2);
    dp[1][1]=1;
    for(int i=1;i<=n;++i) sum[i]=1;
    for(int i=2;i<=n;++i){
        for(int j=1;j<=i;++j){
            if(j==1&&s[i]=='<') continue;
            if(j==i&&s[i]=='>') continue;
            if(s[i]=='<'){
                dp[i][j]=(dp[i][j]+sum[j-1])%mod;
            }
            else{
                dp[i][j]=(dp[i][j]+sum[i-1]-sum[j-1]+mod)%mod;
            }
        }
        for(int j=1;j<=n;++j) sum[j]=(sum[j-1]+dp[i][j])%mod;
    }
    printf("%d\n",sum[n]);
    return 0;
}