挺好的一道DP。
/* 2217 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std; #define MAXN 2005
#define MAXM 100005 int lt[MAXN], rt[MAXN];
int ldp[MAXM], rdp[MAXM];
int ln, rn, zn; int main() {
int n, t;
int i, j, k, tmp;
int ans; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif while (scanf("%d %d", &n, &t) != EOF) {
ln = rn = ;
zn = ;
lt[] = ;
rt[] = ;
for (i=; i<n; ++i) {
scanf("%d", &k);
if (k > )
rt[rn++] = k;
else if (k < )
lt[ln++] = -k;
else
++zn;
} rt[] = ;
lt[] = ;
sort(rt, rt+rn);
sort(lt, lt+ln);
ldp[] = ;
rdp[] = ; k = ;
for (i=; i<ln; ++i) {
for (j=lt[i-]; j<lt[i]; ++j)
ldp[j] = k;
++k;
ldp[j] = k;
} k = ;
for (i=; i<rn; ++i) {
for (j=rt[i-]; j<rt[i]; ++j)
rdp[j] = k;
++k;
rdp[j] = k;
} ans = -;
// go left and back to right
for (i=; i<=lt[ln-]; ++i) {
if (t < i)
break;
k = t-(i+i);
if (k < )
k = ;
if (k > rt[rn-])
k = rt[rn-]; ans = max(ans, ldp[i]+rdp[k]);
}
// go right and back to left
for (i=; i<=rt[rn-]; ++i) {
if (t < i)
break;
k = t-(i+i);
if (k < )
k = ;
if (k > lt[ln-])
k = lt[ln-]; ans = max(ans, rdp[i]+ldp[k]);
}
// go zero point first
ans += zn; printf("%d\n", ans);
} return ;
}
【HDOJ】2217 Visit的更多相关文章
-
【HDOJ】4729 An Easy Problem for Elfness
其实是求树上的路径间的数据第K大的题目.果断主席树 + LCA.初始流量是这条路径上的最小值.若a<=b,显然直接为s->t建立pipe可以使流量最优:否则,对[0, 10**4]二分得到 ...
-
【HDOJ】4418 Time travel
1. 题目描述K沿着$0,1,2,\cdots,n-1,n-2,n-3,\cdots,1,$的循环节不断地访问$[0, n-1]$个时光结点.某时刻,时光机故障,这导致K必须持续访问时间结点.故障发生 ...
-
【HDOJ】4351 Digital root
digital root = n==0 ? 0 : n%9==0 ? 9:n%9;可以简单证明一下n = a0*n^0 + a1*n^1 + ... + ak * n^kn%9 = a0+a1+..+ ...
-
【HDOJ】4322 Candy
状态DP显然可以解,发现T了,不知道优化后能不能过.然后发现费用流可以解.trick是对need拆解成need/K, need%K两种情况讨论. /* 4312 */ #include <ios ...
-
【HDOJ】5296 Annoying problem
LCA+RMQ.挺不错的一道题目. 思路是如何通过LCA维护费用.当加入新的点u是,费用增量为dis[u]-dis[lca(u, lower_u)] - dis[lca(u, greater_u)] ...
-
【HDOJ】3948 The Number of Palindromes
后缀数组求不重复回文子串数目.注意dp数组. /* 3948 */ #include <iostream> #include <sstream> #include <st ...
-
【HDOJ】4775 Infinite Go
其实是一道模拟题,并查集用来优化.还可以的一道题目. /* 4775 */ #include <iostream> #include <sstream> #include &l ...
-
【HDOJ】2242 考研路茫茫——空调教室
tarjan缩点,然后树形dp一下可解.重点是重边的处理. /* 2242 */ #include <iostream> #include <sstream> #include ...
-
【HDOJ】1518 Square
DFS+剪枝.与HDOJ 1455如出一辙. #include <stdio.h> #include <stdlib.h> #include <string.h> ...
随机推荐
-
PHP操作mysql数据库:[2]查询数据听语音
本文主要详细讲解如何使用php语言,对mysql数据库进行查询.添加.删除.更新等操作. 工具/原料 Macromedia Dreamweaver 8 mysql数据库,php语言 一.前言 ...
-
SQL高级查询之一
一,子查询 SELECT e.emp_id, e.fname, e.lname FROM (SELECT emp_id, fname, lname, start_date, title FROM em ...
-
建造者模式->;代码示例
<?php interface Builder{ public function head(); public function body(); public function foot(); ...
-
PROTEL99 SE生成的gerber 与ncdrill的坐标不对应
导入cam350后的: 解决方法:出gerber的时候在高级选项里面. 1.数据单位及格式 2.优化设置
-
kong介绍-个人分享
kong简介 背景 我们在提供api或微服务时,通常借助openresty nginx进行流量转发或者添加一些规则或功能,但是随着服务数量和引用增多,复杂的网络环境, 使维护变得困难,不容易扩展,一些 ...
-
SpringBoot错误求解决
. ____ _ __ _ _ /\\ / ___'_ __ _ _(_)_ __ __ _ \ \ \ \( ( )\___ | '_ | '_| | ...
-
配置使用dwr完成收邮件提示
DWR(Direct Web Remoting)是一个用于改善web页面与Java类交互的远程服务器端Ajax开源框架,可以帮助开发人员开发包含AJAX技术的网站.它可以允许在浏览器里的代码使用运行在 ...
-
使用EasyNetQ简化RabbitMQ操作
关于具体的操作看查看官方文档:https://github.com/EasyNetQ/EasyNetQ 也可以参考中文翻译版本:http://www.cnblogs.com/HuangLiang/p/ ...
-
Haproxy重刷一次
centos上,yum安装,完全无难度. 只是设置时,要注意一下跳转,和nginx规则差不多. https://blog.csdn.net/qq_28710983/article/details/82 ...
-
Jsの练习-数组常用方法
1. join() 方法: <!DOCTYPE html> <html lang="en"> <head> <meta charset=& ...