解题报告:这道题是个状态机模型的简单题吧,主要题目的细节是买入卖出加起来算是一笔交易,状态转移也不说了,注意一下j-1和j的区别,f[i][j][k]代表前i天的股票已经进行了j次交易,k为0代表当前手里没有股票,k=1时代表手中有股票,初始化把交易次数为0并且手中没有股票的方案都变为0,别的都是非法状态。

AC代码:

#include<iostream>
#include<cstring>
using namespace std;
const   int N=100010,M=110;
int f[N][M][2];
int w[N];
int main()
{
   
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    memset(f,-0x3f,sizeof f);
    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]);
        f[i][j][1]=max(f[i-1][j-1][0]-w[i],f[i-1][j][1]);
    }
    }
    int res=-1e9;
    for(int i=0;i<=k;i++)   res=max(res,f[n][i][0]);
    cout<<res<<endl;
}