优化 [Test, 动态规划]

$优化$优化

$Description$Description

给定长度为 $N$N 的序列 $\left\{a_i\right\}${ai​}, 从中选出 $K$K 个 不相交区间, 从左到右记它们的和为 $s_1,s_2...s_n$s1​,s2​...sn​,
请最大化下述合式
$\sum _{i=1}^{k-1}{s}_i-s_{i+1}$i=1∑k−1​si​−si+1​

$N\&lt;=3\ast 10^4,K\&lt;=min(N,200)$N<=3∗104, K<=min(N,200)

$Solution$Solution

$设F[i,j,k]$设F[i,j,k] 表示前 $i$i 个数, 组成 $j$j 个区间, $(k=0,1,2,3)$(k=0,1,2,3) 的最优值

$k=0$k=0 表示 选择 第 $i$i 个数, $A_{i-1}\&gt;=A_i\&lt;=A_i+1$Ai−1​>=Ai​<=Ai​+1, 最优值,
$k=1$k=1 表示 选择或不选择 第 $i$i 个数, $A_{i-1}\&gt;=A_i\&lt;=A_i+1$Ai−1​>=Ai​<=Ai​+1, 最优值,
即 $0,1$0,1 表示当前数比两边都小时的情况, 只会对答案造成 负贡献.

$k=2$k=2 表示 选择 第 $i$i 个数, $A_{i-1}\&lt;=A_i\&gt;=A_{i+1}$Ai−1​<=Ai​>=Ai+1​, 最优值,
$k=3$k=3 表示 选择或不选择 第 $i$i 个数, $A_{i-1}\&lt;=A_i\&gt;=A_{i+1}$Ai−1​<=Ai​>=Ai+1​ , 最优值.
即 $2,3$2,3 表示当前数比两边都大时的情况, 只会对答案造成 正贡献.

则 $flag=2-(j==1\mid \mid j==K)$flag=2−(j==1  ∣∣  j==K)
$F[i,j,0]=max\left(F\right[i-1,j,0],F[i-1,j-1,3\left]\right)-flag\ast A_{i}F[i,j,1]=max\left(F\right[i,j,0],F[i-1,j,1\left]\right)F[i,j,2]=max\left(F\right[i-1,j,2],F[i-1,j-1,1\left]\right)+flag\ast A_{i}F[i,j,3]=max\left(F\right[i,j,2],F[i-1,j,3\left]\right)$F[i,j,0]=max(F[i−1,j,0],F[i−1,j−1,3])−flag∗Ai​ F[i,j,1]=max(F[i,j,0],F[i−1,j,1]) F[i,j,2]=max(F[i−1,j,2],F[i−1,j−1,1])+flag∗Ai​ F[i,j,3]=max(F[i,j,2],F[i−1,j,3])  

$\begin{array}{}\text{(flag\&gt;1)}& F[i,j,1]=max\left(F\right[i,j,1],F[i-1,j-1,1\left]\right)F[i,j,3]=max\left(F\right[i,j,3],F[i-1,j-1,3\left]\right)\end{array}$F[i,j,1]=max(F[i,j,1],F[i−1,j−1,1])F[i,j,3]=max(F[i,j,3],F[i−1,j−1,3])(flag>1)

紫色部分为 $状态的继承$状态的继承

$Code$Code

$std$std

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define reg register int 
#define rep(i, a, b) for (reg i = a; i <= b; i++) 

const int INF = 1e9, N = 30005, K = 205; 
const double eps = 1e-6, phi = acos(-1.0); 
ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;} 
ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int f[N][K][4];
int main() {
    freopen("optimization.in", "r", stdin);
    freopen("optimization.out", "w", stdout);
	int n = read(), k = read();
	rep(i, 1, k) rep(j, 0, 3) f[0][i][j] = -INF;
	rep(i, 1, n) {   
		int x = read();
		rep(j, 1, k) {             
			int flag = 2 - (j == 1 || j == k);
			f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][3]) - flag * x;//low 
			f[i][j][1] = max(f[i - 1][j][1], f[i][j][0]);//

			f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + flag * x;//high
			f[i][j][3] = max(f[i - 1][j][3], f[i][j][2]);
			if (flag - 1) {
				f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][1]);
				f[i][j][3] = max(f[i][j][3], f[i - 1][j - 1][3]);
			}
		}
	}
	printf("%d\n", max(f[n][k][1], f[n][k][3]));
}