三维滚动数组
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 100010,k=110,INF = 0x3f;
using namespace std;
int f[N][k][2];
int main(){
int n,k;
cin>>n>>k;
//买入为一次交易
memset(f,-INF,sizeof(f));
for (int i = 0; i <= n; i ++ ){
f[i&1][0][0]=0;//第i-1支股票可以一次都不要
}
for (int i = 1; i <= n; i ++ ){
int a;
cin>>a;
for (int j = 1; j <=min(k,i); j ++ ){
f[i&1][j][0]=max(f[(i-1)&1][j][0],f[(i-1)&1][j][1]+a);//手中没有,1.上次手中没有2.上次手中已经有,现在卖了
f[i&1][j][1]=max(f[(i-1)&1][j-1][0]-a,f[(i-1)&1][j][1]);//手中有,1.上次就有,2.上次没有,这次买了
}
}
int res = 0;
for (int i = 0; i <=k; i ++ ){
res = max(res,f[n&1][i][0]);
}
cout<<res;
}
二维,类似背包问题
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 100010,k=110,INF = 0x3f;
using namespace std;
int f[k][2];
int main(){
int n,k;
cin>>n>>k;
//买入为一次交易
memset(f,-INF,sizeof(f));
f[0][0]=0;
for (int i = 1; i <= n; i ++ ){
int a;
cin>>a;
for (int j = min(k,i); j >=1; j -- ){
f[j][0]=max(f[j][0],f[j][1]+a);//手中没有,1.上次手中没有2.上次手中已经有,现在卖了
f[j][1]=max(f[j-1][0]-a,f[j][1]);//手中有,1.上次就有,2.上次没有,这次买了
}
}
int res = 0;
for (int i = 0; i <=k; i ++ ){
res = max(res,f[i][0]);
}
cout<<res;
}