前言
没想到在蓝桥杯的课程找到了 II ,比 IV 和 V简单多了
传送门 :
思路
状态表示 : $f[i][2]$ 表示当前第$i$天是否有股票
显然状态计算很简单
- 没有股票的时候
$f[i][0] = max(f[i-1][1] +w[i],f[i-1][0])$ - 有股票的时候
$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<=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<<f[n][0]<<endl;
}