Atcoder DP Contest T题解

一道需要一定分析的 dp 题目。

atcoder 题目传送门 & 洛谷题目传送门

更好的阅读体验

给定 n n n 和一个长度为 n − 1 n-1 n−1 的字符串（由 ‘<’ 和 ‘>’ 组成），求数列 1 , 2 , . . . , n 1,2,...,n 1,2,...,n 有多少种排列，使得相邻数之间的大小关系与字符串中大于号小于号相符合，答案对 1 0 9 + 7 10^9+7 109+7 取模。

• 1 ≤ n ≤ 3000 1\le n\le 3000 1≤n≤3000

先给出本题的一个重要结论：

对于这一序列的任何一个子序列，在其内部排列时我们只需要关心每个数的大小关系，而不是每个数具体的值。

举例：

序列6,9,11在进行内部排列时，我们可以将其视为1,2,3。

所以：

我们只要考虑上一个数是什么，保证满足大小关系放数就行。

这样我们得到了一个显然的 dp 状态：

• d p i , j dp_{i,j} dpi,j​ 表示考虑到第 i i i 个位置，前面一个数是前面排列中第 j j j 大（上面已经得出结论，第 j j j 大的数就视为 j j j 参与排列）的可能数。
  

  
  

转移：

分为两种情况：当前的数 > 上一个数 & 当前的数 < 上一个数。

• 枚举上一个数在之前序列中大小排名 k k k，通过相对大小关系得到转移方程：

d p i , j = { ∑ k = 1 j − 1 d p i − 1 , k s i − 1 = ′ < ′ ∑ k = j i − 1 d p i − 1 , k s i − 1 = ′ > ′ dp_{i,j}=\begin{cases}\sum\limits_{k=1}^{j-1}dp_{i-1,k}&s_{i-1}='<'\sum\limits_{k=j}^{i-1}dp_{i-1,k}&s_{i-1}='>'\end{cases} dpi,j​=⎩⎪⎪⎨⎪⎪⎧​k=1∑j−1​dpi−1,k​k=j∑i−1​dpi−1,k​​si−1​=′<′si−1​=′>′​

这样转移是 O ( n ) O(n) O(n) 的，需要优化。

观察转移方程不难发现，可以对 d p i − 1 dp_{i-1} dpi−1​ 记录前缀和，然后用前缀和进行转移。

这当然是可以的，但是有代码量更少更好写的做法：

以 s i − 1 = ′ < ′ s_{i-1}='<' si−1​=′<′ 举例，我们比较 d p i , j − 1 dp_{i,j-1} dpi,j−1​ 和 d p i , j dp_{i,j} dpi,j​ 发现可以用他们的差递推，从 d p i , j − 1 dp_{i,j-1} dpi,j−1​ 向 d p i , j dp_{i,j} dpi,j​ 转移 。

s i − 1 = ′ > ′ s_{i-1}='>' si−1​=′>′ 同理，从 d p i , j + 1 dp_{i,j+1} dpi,j+1​ 向 d p i , j dp_{i,j} dpi,j​ 转移。

• 这样，我们就有了新的转移方程：

d p i , j = { d p i , j − 1 + d p i − 1 , j − 1 s i − 1 = ′ < ′ d p i , j + 1 + d p i − 1 , j s i − 1 = ′ > ′ dp_{i,j}=\begin{cases}dp_{i,j-1}+dp_{i-1,j-1}&s_{i-1}='<'\dp_{i,j+1}+dp_{i-1,j}&s_{i-1}='>'\end{cases} dpi,j​={dpi,j−1​+dpi−1,j−1​dpi,j+1​+dpi−1,j​​si−1​=′<′si−1​=′>′​

这样的转移是 O ( 1 ) O(1) O(1) 的。

时间复杂度： O ( n 2 ) O(n^2) O(n2)。

空间复杂度： O ( n 2 ) O(n^2) O(n2)（如果用滚动数组可以降到 O ( n ) O(n) O(n)，但这一题空间足够了）。

#include 
#define ll long long
#define pb push_back
#define pii pair
#define mp make_pair
#define F first
#define S second
using namespace std;
const ll MOD=1e9+7;//取模
int n;
string s;
ll dp[3005][3005],ans;
int main()
{
	cin>>n>>s; 
	dp[1][1]=1ll;//这里数组下标从1开始
	for(int i=2;i<=n;i++)
	{//按上面公式进行递推转移
		if (s[i-2]=='<')
			for(int j=1;j<=i;j++)
				dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%MOD;
		else
			for(int j=i-1;j>=1;j--)
				dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
	}
	for(int j=1;j<=n;j++)
		ans=(ans+dp[n][j])%MOD;//答案为dp[n]总和
	cout<

#include 
#include 
#include 
#include 
using namespace std;

const int mod = 1000000007;

int N; char S[3030];
vector<int> z;//记录每个递增序列长度
//inv为逆元，fact为阶乘，ifact为阶乘逆元
long long inv[3030] = {0,1}, fact[3030] = {1,1}, ifact[3030] = {1,1};
long long prv[3030],nxt[3030];//滚动的dp数组

int main()
{
	scanf ("%d",&N);
	scanf ("%s",S);
	int s = 1;
	for (int i=0;i<N-1;i++){//储存递增序列
		if (S[i] == '<') s++;
		else{
			z.push_back(s);
			s = 1;
		}
	}
	z.push_back(s);
	for (int i=2;i<=N;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}//递推预处理阶乘和逆元
	prv[z.back()] = 1;
	z.pop_back();
	reverse(z.begin(),z.end());
	for (int x : z){
		for (int j=0;j<=N;j++) nxt[j] = 0;
		for (int j=0;j<=N;j++) if (prv[j]){//转移
			nxt[j+x] = (nxt[j+x] + mod - prv[j]) % mod;
			nxt[x] = (nxt[x] + prv[j] * ifact[j]) % mod;
		}
		for (int j=0;j<=N;j++) prv[j] = nxt[j];
	}
	long long sum = 0;
	for (int j=0;j<=N;j++) sum = (sum + prv[j] * ifact[j]) % mod;//求答案
	printf ("%lld\n",sum*fact[N]%mod);
	return 0;
}