[Acwing|蓝桥杯] 1055. 股票买卖 II 线性dp

前言

没想到在蓝桥杯的课程找到了 II ,比 IV 和 V简单多了 传送门 :

思路

状态表示 : f [ i ] [ 2 ] f[i][2] f[i][2] 表示当前第 i i i天是否有股票

显然状态计算很简单

1. 没有股票的时候 f [ i ] [ 0 ] = m a x ( f [ i − 1 ] [ 1 ] + w [ i ] , f [ i − 1 ] [ 0 ] ) f[i][0] = max(f[i-1][1] +w[i],f[i-1][0]) f[i][0]=max(f[i−1][1]+w[i],f[i−1][0])
2. 有股票的时候 f [ i ] [ 1 ] = m a x ( f [ i − 1 ] [ 0 ] − w [ i ] , f [ i − 1 ] [ 1 ] ) f[i][1] =max(f[i-1][0] -w[i],f[i-1][1]) f[i][1]=max(f[i−1][0]−w[i],f[i−1][1])

CODE

const int N  = 1e5+10;
int f[N][2],a[N];
int n;
void solve()
{
	cin>>n;
	for(int i=1;i>a[i];
	}
	memset(f,-0x3f,sizeof f);
	
	f[0][0] = 0;
	
	for(int i=1;i