1 条题解
-
0
[T] Permutation(dp_t)题解
题意简述
给定长度 的
</>串,求满足相邻比较关系的 排列个数 。思路
状态设计
一个关键技巧:只关心最后一位在已用数字中的相对排名,而不关心具体值。设
$$f_{i,j} = \text{用 } 1..i \text{ 构成的前缀排列中,末尾元素在 } 1..i \text{ 中排名为 } j \text{ 的方案数}.$$转移
处理第 位(对应 的第 个字符):
- 若
<(要求 ):上一位排名 :
- 若
>(要求 ):上一位排名 :
前者用前缀和、后者用后缀和, 转移。答案 。
为什么"相对排名"够用
插入新元素时,原有元素的相对顺序不变;把排名 的新元素插到末尾,"上一位在原 个中的排名"与"在新 个中的排名"之间的比较关系,恰好等价于数值比较。这是本题最精妙的一步。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> using namespace std; const long long MOD = 1000000007LL; int main() { int n; static char s[3005]; scanf("%d %s", &n, s); vector<long long> f(n + 1, 0), pre(n + 2, 0); f[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i - 1; j++) pre[j] = (pre[j - 1] + f[j]) % MOD; for (int j = i; j >= 1; j--) { if (s[i - 2] == '<') f[j] = pre[j - 1]; else f[j] = (pre[i - 1] - pre[j - 1] + MOD) % MOD; } } long long ans = 0; for (int j = 1; j <= n; j++) ans = (ans + f[j]) % MOD; printf("%lld\n", ans); return 0; }易错点
- 字符下标错位:处理第 位用的是
s[i-2](0 起)。 <用pre[j-1],>用pre[i-1] - pre[j-1]——符号写反是最常见错误。- 倒序更新
f[j],或先把pre算好(本解先算pre,顺序无关)。 pre每轮只用前 项,别沿用上一轮的长度。
数据说明
共 16 组:3 组官方样例; 的
</>; 全</全>; 的<><; 随机; 随机三组、全<(答案 )、全>(答案 )。 - 若
- 1
信息
- ID
- 29
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者