题解 | #买卖股票的最好时机(四)#

解题思路：

• 分阶段决策，大致可分，0次买卖，1次买卖，k次买卖。决策技巧如上一题。
• 技巧利用-price表示买入价格，决策中使用max取最佳买入价格。
• 如有卖出，假如在i位置卖出，则卖出价格应为在次之前的所有卖出价格中是最优选择即$sel{l}_i=max(sel{l}_{1--i-1},pric{e}_i+bu{y}_i)sell\_i\; =\; max(sell\_\{1--i-1\},price\_i+buy\_i)$
• 将前k-1次卖出的收益汇入到第k次卖出，最后输出最后一次卖出收益即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin>>n>>k;
    vector<vector<int>> dp(k,vector<int>(2));
    int v;
    scanf("%d", &v);
    for(int i = 0; i < k; ++i){
        dp[i][0] = -v;
        dp[i][1] = 0;
    }
    for(int i = 1; i < n; ++i){
        scanf("%d", &v);
        dp[0][0] = max(dp[0][0], -v);
        dp[0][1] = max(dp[0][1], dp[0][0] + v);
        for(int j = 1; j < k; ++j){
            dp[j][0] = max(dp[j-1][1] - v, dp[j][0]);
            dp[j][1] = max(dp[j][1], dp[j][0] + v);
        }
    }
    cout<<dp[k-1][1]<<endl;
    return 0;
}