1057. 股票买卖 IV

1057. 股票买卖 IV

// 0:无股票  1:有股票
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int w[N];
int f[N][110][2];

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>w[i];
    
    memset(f,-0x3f,sizeof f);
    // for(int j=0;j<=k;j++)f[0][j][0]=0;  //这一行是不要的，必须从j为0的状态转移过来
    for(int i=0;i<=n;i++)f[i][0][0]=0;  // 必须只能从无股票状态转移过来
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i-1]);  // 卖
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i-1]);  // 买
        }
    }
    
    int res=0;
    for(int j=0;j<=k;j++)res=max(res,f[n][j][0]);
    cout<<res;
    
    return 0;
}