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


推荐相关:

NOIP2007提高组试题及解析

NOIP2007提高组试题及解析_IT/计算机_专业资料。NOIP2007 提高组试题和题解NOIP...dp,可以看作类似于石子归并,每次在 2 边 进行合并我们可以把问题转化为每次要...


热力学第一定律小结与复习题解

热力学第一定律小结与复习题解_理学_高等教育_教育...?P ? H 节流膨胀中体系压力总是降低的,即 dp<...热力学第一定律习题讲解 [P127 复习题 T2 讲解] ...


ACM训练之USACO月赛题解_图文

ACM训练之USACO月赛题解_计算机软件及应用_IT/计算机_专业资料。USACO2002-2008...USACO 2003 March 将单词表按长度排序,然后 DP。 Travel Games 题目名称 Best ...


信息学奥林匹克联赛复赛模拟试题及题解

匹​克​联​赛​复​赛​模​拟​试​题​及​题​解...考虑使用 DP: 设两个 DNA 序列分别为 s1,s2,长度分别为 len1,len2,score ...


noip2008普及组复赛试题(附题解)

noip2008普及组复赛试题(附题解)_IT/计算机_专业...1、文件名(程序名和输入输出文件名)必须使用小写。...1<=m<=30 ball.out 2 直接 dp,似乎说递推更...


植物生理学试题集与题解

植物生理学试题集与题解_农学_高等教育_教育专区。...15. 生长抑制物质包括___生长抑制剂___和___生长...①DMAPP+ATP/ADP→iPTP/Ipdp ②iPTP/iPDP →iAMP...


Noip2013题解-顾霆枫

考试在熟悉环境时把它打了下来,题目一发下来我和我的小伙伴都 惊呆了!第一题...DP 怎么样都超时 【问题描述】 花匠栋栋(我很想吐槽)种了一排花,每株花都...


中考试题分类题解

中考试题分类题解题型部分 1、小明同学在上楼梯...如果线段 MN 被点 P 分成线段 MP 和 PN,且 种...; AC 3 DP 1 ,过 ? (n 为正整数) DC n (...


VB练习题解

VB练习题解_IT认证_资格考试/认证_教育专区。课后练习(含答案) 书后习题及参考...在 QBASIC 中,变量 DP& 属于哪一种类型? A)整形 B)实型 C)双精度型 D)...


NOIP2015提高组解题报告

考虑 DP,f[i][j]表示在前 i 块石头移走 j ...先二分这个距离使其变为判断可行性问题,然后从前往...min T5 子串【题目大意】有两个字符串 A 和 B...

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