用状态机分析法
一遍过
状态机分析法详见我上一篇题解
这里我就直接给出我画的状态机
设计状态
$f[i][0]$表示第i天手里没有票(刚卖出去)对应图中的“没有”
$f[i][1]$表示第i天手里有票(刚买进来) 对应图中的“有”
$f[i][2]$表示第i天是冷冻期之后(手里没有票,但是可以买入票)对应图中的“冷冻期”
几个看似很小但是很有问题的问题
一、入口?(怎样初始化):
一开始是第0天
并且一定是处于可以买票的状态的
$∴f[0][2] = 0$;
其他状态全部负无穷
其实只需要$f[0][0] = f[0][1] = -INF;$
但是我懒得想
而且万一想少了那不gg了
二、出口?(答案取什么):
我比较懒,所以我也没考虑答案应在什么里面取最大值
所以
for(register int i=1; i<=n; i++) {
ans = max(ans,f[i][0]);
ans = max(ans,f[i][1]);
ans = max(ans,f[i][2]);
}
printf("%d\n",ans);
但是稍加思考就会发现
最后一天票子留在手里肯定是不合算的
最后一天要么是我刚刚卖出去,
要么是我处于冷冻期中(或出了冷冻期)
所以答案应该是在$f[n][0]$和$f[n][2]$中选,即
ans = max(f[n][0],f[n][2]);
但是我觉得我上面那个简单粗暴的选答案的方法挺好的
万一自以为是地想出简单的答案结果想少了呢
反正就是多打两行代码也不加复杂度
最后CODE
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n,k,f[N][3],a[N],ans;
int main(){
scanf("%d",&n);
for(register int i=1; i<=n; i++) scanf("%d",&a[i]);
memset(f,-0x3f,sizeof(f));
f[0][2] = 0;
for(register int i=1; i<=n; i++) {
f[i][0] = f[i-1][1]+a[i];
f[i][1] = max(f[i-1][1],f[i-1][2]-a[i]);
f[i][2] = max(f[i-1][0],f[i-1][2]);
}
// for(register int i=1; i<=n; i++) {
// ans = max(ans,f[i][0]);
// ans = max(ans,f[i][1]);
// ans = max(ans,f[i][2]);
// }
// printf("%d\n",ans);
printf("%d\n",max(f[n][0],f[n][2]));
return 0;
}
Orz
入口出口解释的很清楚~
太真实了
链接挂了
我kao,呜呜呜是网站的锅
难道不应该是从有票变到冷冻期再变到无票期吗…
而且冷冻期也不能向冷冻期转移.....
这种定义方式有点乱乱的。。。
这个应该是因为手中无票的状态后面的状态只能是冷冻期的状态,如果手中无票的状态再能自环就自相矛盾,相当于即使过了冷冻期,它实际的数值只能通过冷冻期向后继承。