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

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

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

显然状态计算很简单

没有股票的时候
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])有股票的时候
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])

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