[Acwing] 1057. 股票买卖 IV 状态分析+线性dp

前言

传送门 :

题意

购买和卖出 求最大利润问题 限制条件 : 当前有股票时,只能进行卖出操作无法再度买入

设计状态 : f [ i ] [ j ] [ 2 ] f[i][j][2] f[i][j][2]表示第 i i i天的时候,已经进行了 j j j次交易,当前手上是否有股票

显然状态转移如下 :

• 当前没有股票 f [ i ] [ j ] [ 0 ] = m a x ( f [ i − 1 ] [ j ] [ 0 ] , f [ i − 1 ] [ j ] [ 1 ] + w [ i ] ) f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]+w[i]) f[i][j][0]=max(f[i−1][j][0],f[i−1][j][1]+w[i])
  1. 从上一次没有股票的地方中转移
  2. 就是在当前这天已经卖掉了
• 当前有股票 f [ i ] [ j ] [ 1 ] = m a x ( f [ i − 1 ] [ j ] [ 1 ] , f [ i − 1 ] [ j − 1 ] [ 0 ] − w [ i ] ) f[i][j][1] =max(f[i-1][j][1],f[i-1][j-1][0]-w[i]) f[i][j][1]=max(f[i−1][j][1],f[i−1][j−1][0]−w[i])
  1. 上一次买入的股票就没有卖出 2.当天购入股票

最后在枚举一下所有的购买次数,取得最大利润即可

CODE

#include 
#include 
#include 
#include 
#include 
#include 
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  Pri_m;
typedef pair pii;
typedef vector VI;
map 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>>k;
	for(int i=1;i>w[i];
	init();
	
	for(int i=1;i