状态机

$ 时间复杂度O(NK),空间复杂度O(2NK)$

参考文献

算法提高课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, K = 110, INF = 0x3f3f3f3f;

int n, k, w;
int f[N][K][2];


int main(){
    cin >> n >> k;
    //初始化
    memset(f, -0x3f, sizeof f);
    for (int i = 0 ; i <= n ; i ++) f[i][0][0] = 0;

    for (int i = 1 ; i <= n ; i ++){
        cin >> w;
        for (int j = 1 ; j <= k ; j ++){
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w);
        }
    }

    //遍历答案并输出
    int res = 0;
    for (int i = 0 ; i <= k ; i ++) res = max(res, f[n][i][0]);

    cout << res;
    return 0;
}

空间压缩

状态转移方程发现，状态只和上一层相关，所以我们可以压缩一维空间，使得空间复杂度O(2K)

初始化也只需要初始化f[0][0] = 0,即交易0次，手中无股票的最大值，其余负无穷

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, K = 110, INF = 0x3f3f3f3f;

int n, k, w;
int f[K][2];


int main(){
    cin >> n >> k;
    //初始化
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 1 ; i <= n ; i ++){
        cin >> w;
        for (int j = k ; j >= 1 ; j --){
            f[j][0] = max(f[j][0], f[j][1] + w);
            f[j][1] = max(f[j][1], f[j - 1][0] - w);
        }
    }

    //便利答案并输出
    int res = 0;
    for (int i = 0 ; i <= k ; i ++) res = max(res, f[i][0]);

    cout << res;
    return 0;
}