wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共40篇）

noi.ac89A 电梯

题目思路首先按照\(t\)排序！！！！首先考虑一个暴力\(dp\) 用\(f[i]\)表示前\(i\)个人到达地点所需要的时间。那么就有如下的转移 \[f_i = min_{1 \le j \le i}(max(f_j,t_i) + max\{w_{j + 1} ... w_...

线段树动态规划dp

2019-03-24

0 501

[luogu1020][导弹拦截]

题目位置 https://www.luogu.org/problemnew/show/P1020 题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉...

贪心动态规划dp

2018-04-18

0 406

[luogu1970][花匠]

题目地址 https://www.luogu.org/problemnew/show/P1970 题目描述花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花...

动态规划dp

2018-04-21

0 475

[poj3046][Ant counting数蚂蚁]

题目链接 http://noi.openjudge.cn/ch0206/9289/ 描述 Bessie was poking around the ant hill one day watching the ants march to and fro while gathering f...

动态规划dp

2018-04-25

0 335

摘樱桃

【题目描述】有n个樱桃排成一列，第i个樱桃的甜度为v[i]，你要把n个樱桃分成若干组，其中每一组的樱桃必须相邻。每一组樱桃的美味度为(sum-T)^2 ，其中sum是这组樱桃的甜度之和，T为输入给定的系数。一组方案的美味度为每一组的美味度之和。求可行方案最小的美味度。【输入...

动态规划dp

2018-04-26

0 506

某种数列

某种数列问题 (jx.cpp/c/pas) 1000MS 256MB 众所周知，chenzeyu97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的...

动态规划dp

2018-04-28

0 505

两种石子归并

其实dp是我非常喜欢的一个东西，因为他的代码短小精炼。。。。题目描述 <small>Description</small> 有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价...

动态规划dp

2018-05-04

0 611

斜率优化dp

dp的状态和转移方程就足够让人头疼，却还有一些普通dp复杂度不够优秀的题目要用优化。。。 dp的解题方法似乎只能通过讲解题目来完成。一道例题：洛谷3195 题目描述 P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，...

动态规划dp

2018-08-07

0 546

[hdu2089][不要62]

hdu2089 思路数位dp模板题。从高位往低位进行搜索，用pos记录当前位置，lst记录上个位置的数字，bz记录上个位置是否是6，limit来记录上个位置是否达到了上界(如果达到了，就需要对当前位置的上界进行处理) 代码 #include<cstdio> #include&l...

动态规划dp 数位dp

2018-10-09

0 430

[bzoj1563][诗人小g]

bzoj1563 思路首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制...

动态规划dp 决策单调性

2018-10-12

0 483