cogs 920. [東方S1] 琪露诺
2024-09-03 09:30:49
二次联通门 : 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 ;
}
最新文章
- iframe操作
- 详解shape标签
- event对象的属性
- Ubuntu14.04安装和配置ROS Indigo(一)
- http://www.cnblogs.com/huangcong/archive/2010/06/14/1757957.html
- 使用GitHub进行协同项目开发和开源项目贡献
- Intelli IDEA 使用教程
- mac版MyEclipse的安装及创建web项目
- SpringCache与redis集成,优雅的缓存解决方案
- Navicat Premium 12.1.12.0安装与激活
- [Swift]LeetCode142. 环形链表 II | Linked List Cycle II
- 网络协议与OSI体系结构
- 4、Qt Project之串口数据传输
- 1.1初识python
- underscore.js源码解析【函数】
- Linux远程访问及控制(SSH)
- jackson JsonPropertyOrder和@JsonIgnoreProperties注解
- EasyMall 项目记录-环境搭建
- 【原】通过Dubbo注解实现RPC调用
- Android intent action大全