DpAekdyCoin的空间

文章列表

您正在查看 "Dp" 分类下的文章

【SCOI2008】【着色方案】

2010/07/26 22:01

 【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1079

【题目大意】
给出k种颜料，每种Ci份,去涂木块，现在要求相邻的2个颜色必须不同
求方案数mod P (P = 1000000007)

当时看到这题一度YY 公式，可惜到最后都没YY出来，今天看了一

阅读全文>>

类别：Dp|评论(0) |浏览(747)

【HAOI2007】【上升序列】【LIS入门】

2010/07/20 11:05

【题目地址】

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1046

【题目大意】
给出一个序列，求其中长度为L的字典序最小的递增子序列

【解题思路】

倒着做一次最长递减子序列的DP,可以得到DP[i]：表示i到n的序列中以i开头的序列的能到达的最长的递增子序列的长度。复杂度O(nlogn)
于是不难得到算法
对于每次查询，暴力按照字典顺序扫描一次，假设当前的长

阅读全文>>

类别：Dp|评论(0) |浏览(456)

【VIJOS 1218】【数字游戏】

2010/07/16 23:14

【题目地址】

http://www.vijos.cn/Problem_Show.asp?id=1218

【题目大意】
给出N个数字(环形数字)，要求分为M堆，同时求出把每一堆的和加起来以后mod 10 的积最大or 最小
N <= 50, M <= 9

【解题思路】

把那N个数字扩展成2N个数字，之后枚举第一堆的"起点",然后只需要用一个简单的DP来计算最大/最小值
假设
f[i][j] 表示前i 个数字分配成j堆的最小值
g[i][j] 表示前i 个数字

阅读全文>>

类别：Dp|评论(0) |浏览(319)

【BeiJing2010组队】【次小生成树 Tree，倍增,DP,LCA】

2010/06/25 10:37

【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1977

【题目大意】
求一颗树的严格次小生成树

规模 |V| <= 100000, |E| <= 300000

【做法】

(1) 先对于所有的边排序，之后kruskal，并同时记录下该MST
(2) 随便找个root,遍历树，之后再遍历的同时同时进行3个转移
a. LCA中倍增的转移 f[i,j] 表示i的第2^j个父亲的编号，-1表示不存在,其中i

阅读全文>>

类别：Dp|评论(0) |浏览(605)

【ZOJ 2672 Fibonacci Subsequence】【DP , Hash】

2010/06/24 17:59

【题目地址】

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1672

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1987 (俺认为是加强版)

【题目大意】
一个整数序列A1..AN,对于任意的i>=3.有Ai=Ai- 1+Ai-2则称序列A为一个Fib数列
一个序列Ab1...Abk，如

阅读全文>>

类别：Dp|评论(0) |浏览(416)

【ZOJ 3349 Special Subsequence】【除草，线段树，DP】

2010/06/19 18:38

【前言】
此题完全为除草，看来我的编码能力越来越蒟蒻了……

【题目地址】

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3820
【题目大意】

给出一个序列（长度<=10^5),求出最长的序列，满足任意相邻的2项的差的绝对值不超过D

【解题思路】

DP[i] = max{ DP[j] } + 1 满足( j < i && num[i] - D <= num[j] <= num[i] + D)

阅读全文>>

类别：Dp|评论(0) |浏览(526)

【转】[Sdoi2010 地精部落]动态规划

2010/06/02 22:24

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1925
【算法分析】
F[i][j][k]表示第i段，在剩余的 n - i个数字中,小于当前选择的那个数的个数是j，k代表是下一个该上升还是下降，的方案数。
然后转移就行了。
然后需要用滚动数组优化。
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【CODE】

#include <cstdio

阅读全文>>

类别：Dp|评论(0) |浏览(378)

【Apio2010 特别行动队】【DP 斜率优化】

2010/05/20 20:03

【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1911

【题目大意】
给定n个数字,把它们分为若干组,记每组的和为Xi,那么计算最小

使之最大.(假设最优情况下分为了m组)

【解题思路】
【思路1】
朴素动态规划
不难得到一个朴素的动态方

阅读全文>>

类别：Dp|评论(0) |浏览(10686)

【WHUPC2010】【D Hotel】【疯狂DP】

2010/04/25 20:51

【题目地址】

http://acm.hdu.edu.cn/showproblem.php?pid=3390

【题目大意】
求K位10进制数中unluck number 的平方和

【解题方法】
题目的意思十分清晰，于是构造DFA

其中：
1 : 表示以 1结尾的状态
13 : 以13结尾的状态
*表示其他状态

于是可以得到一

阅读全文>>

类别：Dp|评论(0) |浏览(712)

【hust月赛】【A】【Group】

2010/04/05 22:55

【题目地址】
http://210.42.106.193/thx/problem.php?id=1351

【题目大意】
给出一个长为N 的序列，现在需要把它分成至多 K 段，并有每段内的元素个数不小于L
(1<=L<=N<=20000, 1<=K<=100)

【解题思路】
一开始想到了斜率优化，可是搞了半天发现连四边形都不满足，也就是基本就不单调，能过就神奇了……

首先可以想到最朴素的DP
复杂度 O(N^2* K)

阅读全文>>

类别：Dp|评论(0) |浏览(393)

[SCOI2009]windy数

2010/03/21 0:28

【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1026

【题目大意】
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ (-_-就是题目)
【解决方案】
不难观察到某一位只和自己前面那个位的状态有关，于是很容易想到

阅读全文>>

类别：Dp|评论(0) |浏览(916)

[HNOI2008]Cards

2010/03/03 8:48

【题目地址:】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1004

【题目大意:】
给出N个牌,并且告知你3个数字Sa,Sb(-_-),Sc 表示在对卡片涂色完以后的3种颜色的个数,并且题目保证了总个数 = Sa + Sb + Sc

之后给你M 个置换群, 在这些置换群的作用下得到的方案被认为的相同的.
现在问你所存在的不同的方案数,来达到题目说的要求.输出答案mod P ( P 是素数)

【解题

阅读全文>>

类别：Dp|评论(0) |浏览(909)

[ZJOI2006]物流运输trans

2010/03/02 16:19

【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1003

【题目大意:】
给出一个图(|V|<=20),然后给出若干信息,表示在某一段时间内某些顶点不能使用.
起点是1,终点为n.现在按照某特定路径走(自由选择),如果在某一天你选择的路上面有某个点不在工作
那么你必须再额外花 K 来改变路线(每次改变路线都需要花费K

阅读全文>>

类别：Dp|评论(0) |浏览(530)

[UVA][11762 Race to 1][疯狂DP]

2010/01/24 17:36

【传送门:】
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2862
【题目大意:】
已知D,每次从[1,D]内的所有素数中选择一个Ni,如果D = 0(mod Ni),那么D /= Ni,否则D不变(可以看成是每一轮
D/= GCD(D,Ni) )
【数据组数:】
<=1000
【时间限制:】

阅读全文>>

类别：Dp|评论(0) |浏览(488)

FOJ 1852 Impossible Mission II

2009/11/12 9:59

在神牛lyg(SuperBrother)的亲切指点下终于A了几道状态DP入门题,今天又遇到了一道挺有感觉的入门题:

传送门

图论+状态DP
首先floyd预先处理,对(必须经过的m个点)建立新的图,显然新的图<=16,然后状态dp
dp[i][state_i]表示子图状态中以i结尾,状态为state_i

阅读全文>>

类别：Dp|评论(0) |浏览(418)

1 [2] [3] [下一页] [尾页]

文章分类

默认分类(26)

Acm(3)

Usaco(11)

数论(34)

图论(39)

贪心(3)

计算几何(21)

Dp(32)