「AGC040E」Prefix Suffix Addition 题解 (DP)
题目简介
你有一个长为 \(N\) 的序列 \(x_1,x_2,\dots,x_N\),一开始全部为 0，你现在可以以任意顺序进行任意次以下两种操作：
- 选定整数 \(k(1\le k\le N)\) 与不下降非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\le i \le k\)，令 \(x_i\) 加上 \(c_i\)。
- 选定整数 \(k(1\le k\le N)\) 与不上升非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\le i \le k\)，令 \(x_{N-k+i}\) 加上 \(c_i\)。
问最少进行多少次操作使得最后对任意 \(i\) 有 \(x_i=A_i\)。
转化
0x1.
由于 \(x\) 的初始值全为 \(0\) ，所以可以考虑将其翻一转，变成
- 选定整数 \(k(1\le k\le N)\) 与不上升非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\le i \le k\)，令 \(x_i\) 加上 \(c_i\)。
- 选定整数 \(k(1\le k\le N)\) 与不下降非负序列 \(c_1,c_2,\dots,c_k\)，对所有 \(1\le i \le k\)，令 \(x_{N-k+i}\) 加上 \(c_i\)。
这样，对于操作1，可视为 \(c_{k+1}\dots c_N = 0\)
对于操作2，可将\(c_{N-k+1}\dots c_N\)赋值为\(c_1\dots c_k\)，然后令\(c_1\dots c_k =0\)
操作1的所有序列叠加，所得的还是不上升非负序列，记为 \(B\)
操作2的所有序列叠加，所得的还是不下降非负序列，记为 \(C\)
可得 \(A_i=B_i+C_i\)，转换得 \(C_i=A_i-B_i\)，\(A\)已知，DP求 \(B\) 即可。
0x2.
令 \(f_{i,j}\) 表示 DP 到第 \(i\) 个位置，其中 \(B_i=j\) 的最小值。
由：
\[f_{i,B_i}=\min f_{i-1,B_{i-1}}+[B_i不难得出状态转移方程：
\[f_{i,j}=\min f_{i-1,k}+[j变形：
\[f_{i,j}=\min f_{i-1,k}+[j0x3.
由上式可知，\(j\) 越大，越难满足 \(j
也就是说，\(k\) 越小，越容易满足 \(j
另外，对于已知状态\(f_{i-1,k}\)，\(f_{i,j}\) 只可能有三种值：
- \(f_{i-1,k}\)
- \(f_{i-1,k}+1\)
- \(f_{i-1,k}+2\)
换句话说，如果对于 \(f_{i,j}\) ，有 \(f_{i,j'}
0x4
偷换概念：
使用 \(f_{i,j}\) 表示，当DP到前 \(i\) 位，最小值为 \(j\) 时对应的 \(B_i\) 最小值。
即 将原本的\(f_{i,j}\)概念调换一下。
使用map进行DP。
\(AC\ Code\)
#include
#include
#include