yxc老师提供了直接计算的思路,看算法提高课视频即可
这里提供一个转化的思路,题目要求 最多连续选k个使效率最大
可以转化为 每k + 1个里必须不选 1 个,使不选的总效率最小,最后用总效率减去不选的效率即可
f[i]表示不选第i个的最小不选效率,从前k + 1个里转移即可,可以参考 烽火传递 这道题
ac代码:
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int q[N],n,m;
LL ans,f[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
{
scanf("%d",&f[i]);
ans += f[i];
}
int tt = 0,hh = 0;
for(int i = 1;i <= n;i ++)
{
if(i - q[hh] > m + 1)hh ++;
f[i] += f[q[hh]];
while(tt >= hh && f[q[tt]] >= f[i])tt --;
q[++ tt] = i;
}
LL res = 1e18 + 7;
for(int i = n - m;i <= n;i ++)
res = min(res,f[i]);
cout << ans - res;
}
明白了,不选第i个的最小不选效率 就是 不选第i个的最小损失的效率,那么第i个不选就损失了f[i],那么上一个不选的在[i-(m+1),i-1]区间内,取一个最小的损失就是f[q[hh]],所以f[i]+=f[q[hh]]
感谢, 我明白了!!
[i-(m+2)+1,i-1]
这个比较好理解!!
妙啊妙啊%%%%%
#### 确实妙
orz
太聪明了叭!!!!orz
tql
这样感觉确实方便一点。
f[i] += f[q[hh]]; f[i]定义不是说不选第i个吗?这里 += 的意义是?求解答巨巨
这里的含义是不选第i个的情况下的最小不选效率,可以再看一下
这里的含义是不选第i个的情况下的最小不选效率,可以再看一下
我y总的没听懂 看你的一下子就明白了了 爱你爱你
谢谢 加油
谢谢 加油
思路很棒。同学,感觉还可以写的更精简一些
嗯
我也是这么做的,😀
棒~