状态机
算法思路
如果用朴素的dp直接定义状态dp[i][j]表示前i天且完成了j次交易,因为题目对状态有限制:买入和卖出
必须交替,而dp[i][j]不能表示两种状态,所以我们要把混沌的状态拆分成明确的状态.
首先状态的定义就比较巧妙.我们不能直接定义状态为买入股票和卖出股票,否则交易只能两天一次,不能
表示某两天状态相同的情况.
我们把状态定义为:手中有票和手中无票(用1和0表示),那么状态从1->0表示一次卖出,从0->1表示一次买入.
!因为一次交易定义为买入+卖出,而在初始状态我们首先要买入,所以这里以买入作为交易次数的变化(+1).
ysDP
状态定义:
f[i][j][0]:在第i天经过了j次交易,当前手上无票.
f[i][j][1]:在第i天经过了j次交易,当前手上有票.
状态转移:
状态定义:
dp[i][j][k]:在状态机上经过i条边,从0->1的次数为j,且当前状态为k的所有状态
时间复杂度
O(nk)
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, K = 110;
int n, k;
int w[N];
int dp[N][K][2];
int main()
{
scanf("%d%d",&n,&k);
for( int i = 1; i <= n; i++ ) scanf("%d",&w[i]);
memset(dp,-0x3f,sizeof dp);
for( int i = 0; i <= n; i++ ) dp[i][0][0] = 0;//合法状态(前i天停留在0状态)
for( int i = 1; i <= n; i++ )
{
for( int j = 1; j <= k; j++ )
{//先现有买入才有卖出,j从1开始
dp[i][j][0] = max( dp[i-1][j][0], dp[i-1][j][1] + w[i] );
dp[i][j][1] = max( dp[i-1][j][1], dp[i-1][j-1][0] - w[i]);//以买入作为
//交易数量的变化
}
}
int res = 0; //至少不亏
for( int i = 0; i <= k; i++ ) res = max( res, dp[n][i][0] );//完整交易i次
printf("%d\n",res);
return 0;
}