二次联通门 : cogs 920. [東方S1] 琪露诺

/*
cogs 920. [東方S1] 琪露诺 dp 方程为dp[i] = max (dp[i - L], dp[i - L + 1] .... dp[i - R - 1], dp[i - R]); 要用单调队列优化 记录路径是只需像最短路问题一样记录前驱
后递归打印即可
*/
#include <cstring>
#include <cstdio> void read (int &now)
{
register char word = getchar ();
bool temp = false;
for (now = ; word < '' || word > ''; word = getchar ())
if (word == '-')
temp = true;
for (; word >= '' && word <= ''; now = now * + word - '', word = getchar ());
if (temp)
now = -now;
} //#define Online
#define INF 1e9 int N, L, R, Answer = -INF; int pos;
#define Max 1000001
int dp[Max]; int Queue[Max];
int Head, Tail; int value[Max], pre[Max]; void Print_road (int now)
{
if (pre[now] != -)
Print_road (pre[now]);
printf ("%d ", now);
} int main (int argc, char *argv[])
{ #ifdef Online freopen ("iceroad.in", "r", stdin);
freopen ("iceroad.out", "w", stdout); #endif read (N);
read (L);
read (R); for (int i = ; i <= N; i ++)
read (value[i]);
Tail = ; memset (pre, -, sizeof pre);
for (register int i = L, res; i <= N; i ++)
{
if (i - L <= )
continue;
res = dp[i - L];
for (; Head <= Tail && (Queue[Head] + L > i || (Queue[Head] + R < i) || (Queue[Head] > i)); Head ++);
for (; Head <= Tail && (res > dp[Queue[Tail]]); Tail --);
Queue[++ Tail] = i - L;
pre[i] = Queue[Head];
dp[i] = value[i] + dp[Queue[Head]];
if (Answer < dp[i])
{
Answer = dp[i];
pos = i;
}
} printf ("%d\n", Answer);
Print_road (pos);
printf ("-1"); return ;
}

最新文章

  1. iframe操作
  2. 详解shape标签
  3. event对象的属性
  4. Ubuntu14.04安装和配置ROS Indigo(一)
  5. http://www.cnblogs.com/huangcong/archive/2010/06/14/1757957.html
  6. 使用GitHub进行协同项目开发和开源项目贡献
  7. Intelli IDEA 使用教程
  8. mac版MyEclipse的安装及创建web项目
  9. SpringCache与redis集成,优雅的缓存解决方案
  10. Navicat Premium 12.1.12.0安装与激活
  11. [Swift]LeetCode142. 环形链表 II | Linked List Cycle II
  12. 网络协议与OSI体系结构
  13. 4、Qt Project之串口数据传输
  14. 1.1初识python
  15. underscore.js源码解析【函数】
  16. Linux远程访问及控制(SSH)
  17. jackson JsonPropertyOrder和@JsonIgnoreProperties注解
  18. EasyMall 项目记录-环境搭建
  19. 【原】通过Dubbo注解实现RPC调用
  20. Android intent action大全

热门文章

  1. 【转】Webpack 快速上手(中)
  2. 英语muttonfatjade羊脂玉muttonfatjade单词
  3. java学习(2):类和对象
  4. selenium.获取浏览器大小、设置浏览器位置、最大化浏览器
  5. MyCat教程一:MyCat的简单介绍
  6. rest framework 之路由系统
  7. 记python 使用腾讯ocr 识别代码报错 CERTIFICATE_VERIFY_FAILED
  8. Vagrant+VirtualBox虚拟环境
  9. Android Binder机制彻底梳理二
  10. ArcGIS 生成要素轮廓线掩膜