// 空間優(yōu)化

#include<iostream>

#include<cstring>

using namespace std;

const int N = 100010, M = 110;

int w[N], f[M][2];

int main() {

int n, k;

cin >> n >> k;

for (int i = 1; i <= n; i++) cin >> w[i];

for (int j = 0; j <= k; j++) f[j][1] = -1e6;

for (int i = 1; i <= n ; i++)

for (int j = 1; j <= k ; j++) {

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);

?? f[j][0] = max(f[j][0], f[j][1] + w[i]);

}

cout << f[k][0];

}

#include<iostream>

#include<cstring>

using namespace std;

const int N = 100010, M = 110;

int w[N], f[N][M][2];

int main() {

int n, k;

cin >> n >> k;

for (int i = 1; i <= n; i++) cin >> w[i];

for (int j = 0; j <= k; j++) f[0][j][1] = -1e6;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= k; j++) {

f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);

f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);

}

cout << f[n][k][0];

}//三維保證正確

j++ 正序,先更新f[j][0]再更新f[j][1]

for (int j = 1; j <= k ; j++) {

??f[j][0] = max(f[j][0], f[j][1] + w[i]);

?? f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);\\交換順序也是正確

f[j][0] = max(f[j][0], f[j][1] + w[i]); f[j][0]相當(dāng)于f[i-1][j][0],f[j][1] + w[i]相當(dāng)于f[i-1][j][1] + w[i]

f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);// 原代碼

f[j][0] = max(f[i-1][j][0], f[i-1][j][1] + w[i]);// 實際代碼與原代碼等價

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]相當(dāng)于f[i-1][j][1],f[j - 1][0] - w[i]相當(dāng)于f[i][j - 1][0] - w[i]

f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);原代碼

f[i][j][1] = max(f[i - 1][j][1], f[i][j - 1][0] - w[i]);滾動數(shù)組等價代碼,滾動數(shù)組的更新有些數(shù)偏大

f[i][j - 1][0] - w[i]必然大于等于f[i - 1][j - 1][0] - w[i]

f[j][0]更新正確,f[j][1]更新錯誤

j++ 正序,先更新f[j][1]再更新f[j][0]

for (int j = 1; j <= k ; j++) {

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);\\交換順序也是正確

??f[j][0] = max(f[j][0], f[j][1] + w[i]);

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1];f[j][1]存的是舊值f[i - 1][j][1], f[j - 1][0] - w[i] 存儲f[i][j - 1][0] - w[i];

f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);//原代碼

f[j][1] = max(f[i - 1][j][1],f[i][j - 1][0] - w[i])?//滾動數(shù)組某些值必然偏大更新

f[j][0] = max(f[j][0], f[j][1] + w[i]); f[j][1]相當(dāng)于f[i-1][j][0],f[j][1] + w[i]相當(dāng)于 max(f[i - 1][j][1]+w[i],f[i][j - 1][0])

f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + w[i]); // 原代碼

f[j][0] = max( f[i-1][j][0], f[i-1][j][1]+w[i],f[i][j - 1][0])// 按理說大于等于原代碼才行

多了個這玩意f[i][j - 1][0]

f[i][j][0]??前i天,交易了j筆,手頭無票 肯定大于?前i天,交易了j-1筆,手頭無票?

max(f[i-1][j][0], f[i-1][j][1]+w[i])>= f[i][j - 1][0]

f[j][1]更新錯誤,f[j][0]更新正確

如果這個可行,就保證了正確性f[j][0]

?

是什么保證了滾動數(shù)組的正確性,不光是正序還是逆序,更新位置交換也一樣

j-- 逆序,先更新f[j][0]再更新f[j][1]

for (int j = k; j >=1?; j--) {??

??f[j][0] = max(f[j][0], f[j][1] + w[i]);

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);

}

f[j][0] = max(f[j][0], f[j][1] + w[i]);?f[j][0]存的是舊值f[i - 1][j][0],f[j][1] + w[i]存的是f[i-1][j][1] + w[i]

f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]); //原代碼

f[j][0] = max(f[i - 1][j][0], f[i-1][j][1] + w[i]);實際代碼與原代碼等價

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]存的是舊值f[i-1][j][1],f[j - 1][0] - w[i] 存的是 f[i-1][j - 1][0] - w[i]

f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);// 原代碼

f[j][1] = max(f[i-1][j][1], f[i-1][j - 1][0] - w[i])// 實際代碼與原代碼等價

f[j][0]、f[j][1]都更新正確

j-- 逆序,先更新f[j][1]再更新f[j][0]

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);

f[j][0] = max(f[j][0], f[j][1] + w[i]);

f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);f[j][1]存的是舊值f[i-1][j][1],f[j - 1][0] - w[i] 存的是 f[i-1][j - 1][0] - w[i]

f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);// 原代碼

f[j][1] = max(f[i-1][j][1], f[i-1][j - 1][0] - w[i])// 實際代碼與原代碼等價

f[j][0] = max(f[j][0], f[j][1] + w[i]);f[j][0]存的是舊值f[i - 1][j][0],f[j][1] + w[i]存的是max(f[i-1][j][1]+ w[i], f[i-1][j - 1][0])

f[j][0] = max(f[i - 1][j][0], f[i-1][j][1]+ w[i], f[i-1][j - 1][0]);

更新f[j][0]就是更新f[i][j][0] ,也是多了一個這玩意?f[i-1][j - 1][0] ,?max(f[i - 1][j][0], f[i-1][j][1]+ w[i])>= f[i-1][j - 1][0]

f[j][1]正確,f[j][0]正確