专栏文章

CF1032C Playing Piano

AAutream
CF1032C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miowy5ke
此快照首次捕获于
2025/12/03 02:30
3 个月前
此快照最后确认于
2025/12/03 02:30
3 个月前
查看原文

题意简述

给定长度为 nn 的序列 aa，构造一个满足以下条件的 bb，或者输出无解：
  • bi∈[1,5]b_i \in [1, 5]；
  • 若 ai<ai+1a_i < a_{i + 1}，则 bi<bi+1b_i < b_i + 1；
  • 若 ai>ai+1a_i > a_{i + 1}，则 bi>bi+1b_i > b_i + 1；
  • 若 ai=ai+1a_i = a_{i + 1}，则 bi≠bi+1b_i \neq b_i + 1。

题目分析

构造方案如果不能以下想出来的话可以先考虑判断合法性。每一位 bib_i 的取值都与上一位有关，且 bib_i 的值域只有 5，因此考虑 DP。
设 dpi,j=1/0dp_{i, j} = 1/0 表示第 ii 位填 jj 是否可行，由前一位转移，方程显然。
接下来考虑如何记录方案。只需要将每次选择的数据记录到 DP 数组里面就行。
改设 dpi,j=sdp_{i, j} = s，其中 s∈[20,24]s \in [2 ^ 0, 2 ^ 4]，ss 的第 k−1k - 1 位为 1 表示可以从前一个 bib_i 填 kk 的情况转移过来；反之亦然。
状态转移方程：
dpi,j={∑k=1j−1[dpi−1,k≠0]×2k, (ai>ai−1)∑k=j+15[dpi−1,k≠0]×2k, (ai<ai−1)∑k=15[j≠k∧dpi−1,k≠0]×2k, (ai=ai−1)dp_{i, j} = \begin{cases} \sum \limits _{k = 1} ^{j - 1} [dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i > a_{i - 1}) \\ \sum \limits _{k = j + 1} ^{5} [dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i < a_{i - 1}) \\ \sum \limits _{k = 1} ^{5} [j \neq k \land dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i = a_{i - 1}) \\ \end{cases}
最后 DFS 从后往前搜一遍统计路径即可。
时间复杂度 O(n)O(n)。

AC Code

CPP
CI N = 2e5 + 5;
int n, a[N], dp[N][6];
std::vector<int> v;
void dfs(int step, int finger) {
	if(step == 1) {
		std::reverse(all(v));
		for(int i : v) printk(i);
		exit(0);
	}
	rep(i, 1, 5) if((dp[step][finger] >> i - 1) & 1) v.p_b(i), dfs(step - 1, i), v.pop_back();
}
signed main() {
	n = read();
	arrin(a, n);
	rep(i, 1, 5) dp[1][i] = 1;
	rep(i, 2, n) rep(j, 1, 5)
		if(a[i] < a[i - 1]) rep(k, j + 1, 5) dp[i][j] |= !!dp[i - 1][k] << k - 1;
		else if(a[i] > a[i - 1]) rep(k, 1, j - 1) dp[i][j] |= !!dp[i - 1][k] << k - 1;
		else rep(k, 1, 5) if(k != j) dp[i][j] |= !!dp[i - 1][k] << k - 1;
	bool flag = 0;
	rep(i, 1, 5) flag |= dp[n][i];
	if(!flag) puts("-1"), exit(0);
	dp[n + 1][0] = -1;
	dfs(n + 1, 0);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...