wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共38篇）

[luogu1020][导弹拦截]

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

贪心动态规划dp

2018-04-18

0 550

[luogu1970][花匠]

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

动态规划dp

2018-04-21

0 620

摘樱桃

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

动态规划dp

2018-04-26

0 483

[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 610

某种数列

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

动态规划dp

2018-04-28

0 593

两种石子归并

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

动态规划dp

2018-05-04

0 417

斜率优化dp

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

动态规划dp

2018-08-07

0 404

[codevs3342][绿色通道]

codevs3342 思路：既然是要求最小化最长空题段，直接二分答案。然后就是check函数的写法。先考虑n方转移，假设当前二分的答案是x，用f[i]表示前i个题，第i道题写的最小花费时间。最后再去判断后f数组的后x个值是否小于等于要求时间的。然后返回。 int check(int x)...

动态规划dp 单调队列

2018-10-07

0 531

[bzoj4709][柠檬]

bzoj4709 思路首先，最优秀的分法一定是每段两端都是这一段中最多的那个，否则可以把不是的那个踢出去单独成段肯定会更优秀。然后就成了将这个序列分段，保证每段两端元素相同的最大收益和。用a[i]记录第i个位置上的数，用s[i]记录前i个元素中a[i]出现的次数。f[i]表示以前i个数的最...

动态规划dp 决策单调性

2018-10-08

0 427

[hdu2089][不要62]

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

动态规划dp 数位dp

2018-10-09

0 475