tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

DP例题及题解


旅行
(trival.c/trival.cpp/trival.pas) Time Limit: 1s Memory Limit: 32655KB 刚刚开始暑假的 miss. D 从学校出发旅行,她有 n 个景点备选。 学校到每个景点都有一条路,相邻景点之间也有一条路(包括 n 号与 1 号景点之间) 。 假设走每一条路的都要花费 1 元。花费了 m 元后,miss. D 回到学校的方案有几种(方案数对 1000000009 取模)? PS 粗心的 Miss. D 可能中途发现忘带了东西,还要返回学校;而且她不记得某一个景点是 否参观过,可能会多次参观同一个景点

输入 [trival.in] 两个自然数 N M (N 表示 n 个景点(N<=1000),M 表示共花费了 M 元) 对于 30%的数据,M<=100 对于 70%的数据,M<=1000 对于 100%的数据,M<=10000 输出 [trival.out] 一个数,表示从学校出发回到学校的方案数。 样例输入 34 样例输出 21

数轴上的木棒
(line.c/line.cpp/line.pas) Time Limit: 1s Memory Limit: 32655KB

Miss D 给了 gnaw n 根木棒,并告诉他每根木棒的左右点在数轴的坐标。还要求 gnaw 从中 挑出 m 根,使这 m 根任意木棒中的任意两根都不会重叠。Miss D 希望这个 m 尽可能得大, gnaw 不知道该怎么做,但是还是希望能知道最大的 m 是多少,聪明的你能告诉他吗? 输入 [line.in] 第一行一个整数 n 之后 n 行,每行两个整数 l r,表示线段的左右端点。 (0<=l<r<=1e9) 对于 30%的数据 n<=10 对于 50%的数据,n<=1000 对于 100%的数据,n<=200000 输出格式 [line.out] 一个整数 x,表示最多可以选出 x 条相互不覆盖的线段 样例输入 3 12 23 13 样例输出 2 PS 样例中,选[1 2] 和[2 3] 两根木棒符合要求。

单身
(single.c/single.cpp/single.pas) Time Limit: 1s Memory Limit: 32655KB 单身的 gnaw 不再想单身了,想占卜一下自己还有多长时间才能不再单身。于是他定义了一 个数字中有连续两个数位 1,就称这个数为单身数。(例如,511 是单身数,1010 不是单身 数),他想知道一个区间[L,R]的数字有多少个不是单身的数,聪明的你能告诉他吗? 输入格式 [single.in] 两个数字 LR ( 1 <= L <= R) 表示 gnaw 想询问的区间

对于 30%的数据,R<=1e2 对于 70%的数据,R<=1e6 对于 100%的数据,R<=1e9 输出格式 [single.out] 一个数字,表示这个区间内不是单身数的数字个数 样例输入 10 19 样例输出 9


推荐相关:

DP典型题&详细解析

DP典型题&详细解析_高考_高中教育_教育专区。第七章 动态规划 第一讲 概念及...f 3 (10) =18 第六讲:二维背包及背包问题的应用 习题 7.9/P-239 (1)...


习题与题解

课后习题题解 27页 1财富值 干燥习题与题解 11页 1财富值 习题及题解 暂无...2 p A ? p A 0 dp t dp = ?2 A dt dt n 1 dn A 解: ( ?rA...


DP问题

DP问题_计算机软件及应用_IT/计算机_专业资料。...有的题目我们采用动态规划,而有的题目我们则需要用...【题 3】装箱问题 有一个箱子容量为 V(正整数,...


dp算法思想及运用实践例题

dp算法思想及运用实践例题_IT/计算机_专业资料。一...如果问题的最优解所包含的子问题的解也是最优的,...那么,根据题意“每一发炮弹都不能高于前一发的...


acm中dp问题简单入门讲解

严格的说,动态规划程序设计是对解最优化问题的一种...[i]}; 7 注意此伪代码 01 背包的伪代码极为...dp 的题 下面是例题解析 硬币问题(soj 1787) ...


习题解答

A。 dt dt dt 解 6 《化学反应工程》第二版习题解答 dpR ? dp ? ? 2?...0.0736 ? ? 0.9264 cA 0 1 22 第 17 题中的反应,(1)当 cA0=1.2...


POJ合集14-3-31题目+题解

POJ合集14-3-31题目+题解_计算机软件及应用_IT/计算机_专业资料。POJ合集14-...题解此题深搜和 DP 都能解决: 深搜的话需要几个强有力剪枝条件 1、 第三...


汪志诚(习题解答)

汪志诚(习题解答)_理学_高等教育_教育专区。热力学...N ? ?? dxdydp x dpy e Z1 h2 (1) 其中...解:由⒎13 题已求出单位时间碰在单位面积器壁上,...


《半导体器件》习题及参考答案

《半导体器件》习题及参考答案_理学_高等教育_教育专区...解:Dp=9cm2/s,Dn=6cm2/s Lp ? D p? p ?...二级java考前押密试题89份文档 爆笑大撞脸 超爆笑...


蓝桥杯VIP试题以及答案解析

解题思路: 这题模型是树形动态规划入门题目, dp[i...处位置的(值减1)为指数,以10为底数的幂之和的...(x2)<0, 因此遇到这种情况即是满足情况的解。 [...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com