AcWing 1057. 股票买卖 IV
原题链接
中等
作者:
___9
,
2021-05-17 17:01:52
,
所有人可见
,
阅读 175
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
// 状态机,
static int N = 102, n, m;
static int[] w = new int[100002];
static int[][] f = new int[N][2];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String arr[] = in.readLine().split(" ");
n = Integer.parseInt(arr[0]);
m = Integer.parseInt(arr[1]);
arr = in.readLine().split(" ");
for (int i = 1; i <= n; i++)
w[i] = Integer.parseInt(arr[i - 1]);
for (int i = 0; i <= m; i++) // 初始化,第一次只能从f[0][0]转移过去
f[i][1] = 0xcfcfcfcf;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[j][0] = Math.max(f[j][0], f[j][1] + w[i]);
f[j][1] = Math.max(f[j][1], f[j - 1][0] - w[i]);
}
}
int res = 0;
for (int i = 0; i <= m; i++)
res = Math.max(res, f[i][0]);
System.out.println(res);
}
}