前言
题意
购买和卖出 求最大利润问题
限制条件 :
当前有股票时,只能进行卖出操作无法再度买入
设计状态 :
$f[i][j][2]$表示第$i$天的时候,已经进行了$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],f[i-1][j-1][0]-w[i])$- 上一次买入的股票就没有卖出
- 当天购入股票
最后在枚举一下所有的购买次数,取得最大利润即可
CODE
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define CIT cin.tie(0);
#define COT cout.tie(0);
#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
typedef priority_queue<int,vector<int>,greater<int>> Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 1e5+10,M = 110;
int f[N][M][2];
//当前第i天,交易了j次,目前是否有股票
int n,k;
int w[N];
void init(){
//进行初始化
memset(f,-0x3f,sizeof f);
for(int i=0;i<=n;i++)
f[i][0][0]=0;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>w[i];
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
/**
1.当前没有股票的话
1- 前面的股票 拿到这次来卖
2- 本来就没有股票
**/
f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+ w[i]);
/**
2.当前有股票的话
1- 前面拿过来的 但是没有卖
2- 现在刚买
**/
f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
}
}
int ans = 0;
for(int i=0;i<=k;i++){
ans = max(ans,f[n][i][0]);
}
cout<<ans<<endl;
}
/**mYHeart is my algorithm**/
int main()
{
//int t;cin>>t;while(t -- )
solve();
return 0;
}