插入型 dp
分析排列的权值,如果排列确定,那么每个位置都有自己的贡献,并且无关其他位置的贡献。考虑 dp。从小到大将 \(p_i\) 插入序列中,此时序列会分成若干段,可设 \(f_{i,j}\) 插入了 \(1\cdots i\),序列分成 \(j\) 段的权值和。
转移通常有四种。
- 插入到一段的左边,此时 \(i\) 左右的大小情况确定,下面同理,于是可以转移 \(f_{i,j}=\max(f_{i,j},f_{i-1,j}+b_i+c_i)\)
- 插入到一段的右边,\(f_{i,j}=\max(f_{i,j},f_{i-1,j}+a_i+d_i)\)
- 将两段合并为一段,\(f_{i,j}=\max(f_{i,j},f_{i-1,j+1}+2\times x_{i}+a_{i}+c_{i})\)
- 建新的一段,\(f_{i,j}=\max(f_{i,j},f_{i-1,j-1}-2\times x_i+b_i+d_i)\)
考虑限制 \(s\) 和 \(e\),如果 \(i=s/e\),那么不需要转移所有。还有一些特殊情况,如果 \(i>\max(s,e)\) 并且此时 \(j=1\),那么无法合并;如果 \(i>s\) 且 \(j=1\),那么无法插入到左边;右边同理。
复杂度 \(O(n^2)\)。
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 10;
int n, s, e;
i64 x[N], a[N], b[N], c[N], d[N], f[N][N];
void Solve() {
std::cin >> n >> s >> e;
for(int i = 1; i <= n; i++) std::cin >> x[i];
for(int i = 1; i <= n; i++) std::cin >> a[i];
for(int i = 1; i <= n; i++) std::cin >> b[i];
for(int i = 1; i <= n; i++) std::cin >> c[i];
for(int i = 1; i <= n; i++) std::cin >> d[i];
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
if(i == s) {
f[i][j] = std::min(f[i][j], f[i - 1][j] + x[i] + c[i]);
f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - x[i] + d[i]);
} else if(i == e) {
f[i][j] = std::min(f[i][j], f[i - 1][j] + x[i] + a[i]);
f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - x[i] + b[i]);
} else {
if(!(i > s && i > e && j <= 2)) f[i][j] = std::min(f[i][j], f[i - 1][j - 1] - 2 * x[i] + b[i] + d[i]);
if(!(j == 1 && i > s)) f[i][j] = std::min(f[i][j], f[i - 1][j] + b[i] + c[i]);
if(!(j == 1 && i > e)) f[i][j] = std::min(f[i][j], f[i - 1][j] + a[i] + d[i]);
f[i][j] = std::min(f[i][j], f[i - 1][j + 1] + 2 * x[i] + a[i] + c[i]);
}
}
}
std::cout << f[n][1] << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}
标签:std,i64,min,int,max,CF704B,Ant,插入,Man
From: https://www.cnblogs.com/FireRaku/p/18178386