[codevs3342][绿色通道]
2024-10-13 05:40:49
codevs3342
思路:
既然是要求最小化最长空题段,直接二分答案。然后就是check函数的写法。
先考虑n方转移,假设当前二分的答案是x,用f[i]表示前i个题,第i道题写的最小花费时间。最后再去判断后f数组的后x个值是否小于等于要求时间的。然后返回。
int check(int x) {
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;++i)
for(int j=i-1;j>=0&&j>=i-x-1;--j)
f[i]=min(f[i],f[j]+a[i]);
for(int i=n;i>=n-x;--i)
if(f[i]<=t) return 1;
return 0;
}
然后考虑优化这个dp,可以发现每个f[i]都是从前面x个值中的最小值转移过来的,可以用单调队列维护。
int check(int x) {
Head=1,Tail=1;
f[0]=0;
q[1]=0;
for(int i=1;i<=n;++i) {
while(q[Head]<i-x-1&&Head<=Tail) Head++;
f[i]=f[q[Head]]+a[i];
while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;
q[++Tail]=i;
}
return f[q[Head]]<=t;
}
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=50000+100;
int f[N];//f[i]表示前i道题,第i道题做的最小花费时间
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int n,t;
int a[N];
int q[N],Head,Tail;
int check(int x) {
Head=1,Tail=1;
f[0]=0;
q[1]=0;
for(int i=1;i<=n;++i) {
while(q[Head]<i-x-1&&Head<=Tail) Head++;
f[i]=f[q[Head]]+a[i];
while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;
q[++Tail]=i;
}
return f[q[Head]]<=t;
}
int main() {
n=read(),t=read();
for(int i=1;i<=n;++i) a[i]=read();
int ans=0,l=0,r=n;
while(l<=r) {
int mid=l+r>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
return 0;
}
最新文章
- Debian 7 下安装CodeBlocks12.11
- 【转】常用的shell脚本
- 2015年12月10日 spring初级知识讲解(二)最小化Spring XML配置 注解
- MacPort 的使用
- bootstrap dialog自行控制窗口的关闭
- node相关--WebSocket
- C# IO操作,写入文本到txt文件.
- RAC GI安装,报";Task resolv.conf Integerity";验证失败
- Windows系统定时重开或者关机
- 编写高效的Android代码
- emacs vim IDE
- codeforces 21D. Traveling Graph 状压dp
- PullToRefreshGridView上拉加载、下拉刷新
- [效率]Source insight标题栏中路径显示完整路径的方法
- js修改样式表规则
- Python函数篇(4)之迭代器与生成器
- [enum]enum的用法
- 结识hybrid体验这一年
- UVA10559 Blocks(区间dp)
- [Python设计模式] 第27章 正则表达式——解释器模式
热门文章
- Jmeter(三十一)_数据驱动,业务关联
- CSS 分类 (Classification) 实例
- python基础学习笔记(六)
- use_frameworks!和#use_frameworks!的区别、解决Swift项目中use_frameworks!冲突的问题
- Uniform Generator HDU1014
- 12.25daily_scrum
- Natural Language Generation/Abstractive Summarization
- PHP开发:Eclipse版环境配置
- Software Engineering homework2
- 利用ThreadLocal管理事务