AT_dp_T & UVA1650 & P2467

· · 题解

传送门：

AT_dp_T Permutation

UVA1650 Number String

P2467 地精部落

基本模板：AT_dp_T

题面

给定一个长为 n 的排列的相邻两个数之间的大小关系，求填数方案数。

题解

朴素算法

看到 DP 题，首先应该设计状态。

设 f_{i,j} 为前 i 位的排列，第 i 位填 j 的方案数。

然后就可以想状态转移了。

首先，如果将 j 直接插入 i-1 已经确定的排列，那么就会出现重复的数，所以就可以用最简单的办法：将 i-1 已经确定的排列中，大于等于 j 的数全部加一。

可以考虑上一位填的数是什么，然后将答案汇总到 f_{i,j}。

对于 a_{i} > a_{i-1} 的情况，枚举上一位可能填的数，得到 f_{i,j}=\sum_{k=1}^{j-1} f_{i-1,k}。

对于 a_{i} < a_{i-1} 的情况，由于对于大于等于 j 的数全部都加了一，所以可以从 j 开始枚举其填的数，得到 f_{i,j}=\sum_{k=j}^{i-1} f_{i-1,k}。

最终答案为 \sum_{i=1}^{n} f_{n,i}。

时间复杂度 O(n^{3})，显然过不了。

优化1

看到 f_{i,j} 加的都是上一位一个连续的区间，那么优化就很明显了，套个前缀和在里面，就可以把 O(n) 的转移变成 O(1) 的转移。

由于每一个 f_{i,j} 都加的是一段区间，且这一段区间由 j 的值变化而产生左端点或右端点的变化，那么就不用在设一个前缀和数组了，直接从上一个 j 的区间往下加。

综上：

f_{i,j} = \begin{cases} f_{i,j+1}+f_{i-1,j} & a_{i} < a_{i-1}\\ f_{i,j-1}+f_{i-1,j-1} & a_{i}>a_{i-1} \end{cases}

时间复杂度 O(n^{2})。

优化2

看到 f_{i,j} 只受下标 i-1 的 f 的影响，就可以用滚动数组把一维空间滚掉。

空间复杂度 O(n)。

举一反三

UVA1650

加了一种可能性，就是字符串中有问号，而这个问号可能代表 a_{i} < a_{i-1}，也可能代表 a_{i} > a_{i-1}。

所以，问号代表的是 a_{i} \neq a_{i-1}。

这个就比之前的大于小于好处理多了，由于在枚举 j 时之前对上一位大于等于 j 的部分全部加一，所以此时上一位没有与 j 相等的数，直接把上一位所有答案之和汇总到 f_{i,j} 即可。

转移就将上一位的所有答案之和单开一个变量储存，然后再把这个变量赋值给所有 f_{i,j} 即可。

综上：

f_{i,j} = \begin{cases} f_{i,j+1}+f_{i,j} & a_{i} < a_{i-1}\\ f_{i,j-1}+f_{i-1,j-1} & a_{i}>a_{i-1}\\ \sum_{k=1}^{i-1} f_{i-1,k} & a_{i} \neq a_{i-1} \end{cases}

时间复杂度 O(n^{2})，空间复杂度 O(n)。

P2467

给定一个数 n，求长度为 n 且形为波动数组的排列数。

做过前两题，那么很容易便可以想出这题的解法，就是大于小于号交替排列，然后再用 AT_dp_T 的 DP 式子即可。

注意大于小于号总共有两种排列方式，可以想到这两种方案得到的答案相同，因此只用求一种的答案，然后将其乘 2。

时间复杂度 O(n^{2})，空间复杂度 O(n)。

代码

AT_dp_T

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3002;
const ll p=1e9+7;
int n;
char a[N];
ll f[2][N];
ll ans;
int main() {
    scanf("%d",&n);
    cin>>(a+1);
    f[1][1]=1;
    for(int i=2;i<=n;i++) {
        if(a[i-1]=='>') for(int j=i;j;j--) f[i&1][j]=(f[i&1][j+1]+f[(i-1)&1][j])%p;
        if(a[i-1]=='<') for(int j=1;j<=i;j++) f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][j-1])%p;
    }
    for(int i=1;i<=n;i++) ans=(ans+f[n&1][i])%p;
    printf("%lld",ans);
    return 0;
}

UVA1650

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=1e9+7;
const int N=1002;
int n;
char s[N];
ll f[2][N];
ll ans;
void init() {
    memset(f,0,sizeof f);
    memset(s,0,sizeof s);
    ans=n=0;
    return;
}
int main() {
    while(cin>>(s+1)) {
        n=strlen(s+1)+1;
        f[1][1]=1;
        for(int i=2;i<=n;i++) {
            if(s[i-1]=='I') for(int j=1;j<=i;j++) f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][j-1])%p;
            if(s[i-1]=='D') for(int j=i;j;j--) f[i&1][j]=(f[i&1][j+1]+f[(i-1)&1][j])%p;
            if(s[i-1]=='?') {
                f[i&1][1]=0ll;
                for(int j=1;j<i;j++) f[i&1][1]=(f[i&1][1]+f[(i-1)&1][j])%p;
                for(int j=2;j<=i;j++) f[i&1][j]=f[i&1][1];
            }
        }
        for(int i=1;i<=n;i++) ans=(ans+f[n&1][i])%p;
        printf("%lld\n",ans);
        init();
    }
    return 0;
}

P2467

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4202;
ll p;
int n;
char a[N];
ll f[2][N];
ll ans;
int main() {
    scanf("%d%lld",&n,&p);
    for(int i=1;i<n;i++) {
        if(i&1) a[i]='>';
        else a[i]='<';
    }
    f[1][1]=1;
    for(int i=2;i<=n;i++) {
        if(a[i-1]=='>') for(int j=i;j;j--) f[i&1][j]=(f[i&1][j+1]+f[(i-1)&1][j])%p;
        if(a[i-1]=='<') for(int j=1;j<=i;j++) f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][j-1])%p;
    }
    for(int i=1;i<=n;i++) ans=(ans+f[n&1][i])%p;
    printf("%lld",ans*2%p);
    return 0;
}

完结撒花！！！！