JZYshuraK

未归档

/ 注册

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

[poj1185]炮兵阵地_状压dp

炮兵阵地 poj-1185 　　　　题目大意：给出n列m行，在其中添加炮兵，问最多能加的炮兵数。　　　　注释：n<=100，m<=10。然后只能在平原的地方建立炮兵。　　　　　　想法：第2到状压dp，++。这题显然是很经典的。设状态dp[i][j][k]表示第i行的状态为j，i...

2018-03-14

0 426

[poj3252]Round Numbers_数位dp

Round Numbers poj3252 　　　　题目大意：求一段区间内Round Numbers的个数。　　　　注释：如果一个数的二进制表示中0的个数不少于1的个数，我们就说这个数是Round Number.给定区间l,r<=$2\cdot 10^9$。　　　　　　想法：又是一道...

2018-03-13

0 277

[bzoj1026][SCOI2009]windy数_数位dp

windy数 bzoj-1026 　　　　题目大意：求一段区间中的windy数个数。　　　　注释：如果一个数任意相邻两位的差的绝对值都不小于2，这个数就是windy数，没有前导0。$区间边界<=2\cdot 10^9$。　　　　　　想法：数位dp裸题，何为数位dp? 　　　　　　数...

2018-03-12

0 358

[poj3107]Godfather_树形dp_树的重心

Godfather poj-3107 　　　　题目大意：求树的重心裸题。　　　　注释：n<=50000. 　　　　　　想法：我们尝试用树形dp求树的重心，关于树的重心的定义在题目中给的很明确。关于这道题，我们邻接矩阵存不下，用链式前向星存边，然后对于任选节点遍历，然后在回溯是进行最大值...

2018-03-08

0 323

[poj2342]Anniversary party_树形dp

Anniversary party poj-2342 　　　　题目大意：没有上司的舞会原题。　　　　注释：n<=6000，-127<=val<=128. 　　　　　　想法：其实就是最大点独立集。我们介绍树形dp 　　　　　　　　树形dp就是以节点或者及其子树为信息，进行动...

2018-03-08

0 338

[poj3280]Cheapest Palindrome_区间dp

Cheapest Palindrome poj-3280 　　　　题目大意：给出一个字符串，以及每种字符的加入代价和删除代价，求将这个字符串通过删减元素变成回文字符串的最小代价。　　　　注释：每种字符都是小写英文字符，1<=代价cost<=1000，字符串长度<=2000. ...

2018-03-07

0 307

[jdoj1090]矩阵_区间dp

矩阵 jdoj-1910 　　　　题目大意：给你连续的n个矩阵的长和宽，保证每连续的两个相邻矩阵满足相乘的条件，不能改变题目中矩阵的位置，求将这些矩阵相乘为一个矩阵的最小乘法次数。　　　　注释：1<=n<=500，a,b<=50.定义矩阵A(x,a)和矩阵B(a,y)的乘法次...

2018-03-06

0 278

[bzoj3173]最长上升子序列_非旋转Treap

最长上升子序列 bzoj-3173 　　　　题目大意：有1-n，n个数，第i次操作是将i加入到原有序列中制定的位置，后查询当前序列中最长上升子序列长度。　　　　注释：1<=n<=10,000，开始序列为空。　　　　　　具体的非旋转Treap的讲解：讲解链接　　　　　　想法：...

2018-03-03

0 337

[poj-2985]The k-th Largest Group_Treap+并查集

The k-th Largest Group poj-2985 　　　　题目大意：给你n只猫，有两种操作：1.将两只猫所在的小组合并。2.查询小组数第k大的小组的猫数。　　　　注释：1<=n,m<=200,000. 　　　　　　想法：开始的想法就是用Treap合并，用Treap删...

2018-03-02

0 339

[HNOI2002]营业额统计_Treap

[HNOI2002]营业额统计　　　　题目大意：给你一串n数序列，对于每一个刚输入的数a，找到一个前面的数k，使得|a-k|最小。　　　　注释：$n<=32767，ai<=10^6$。　　　　　　想法：刚学Treap。这道算Treap的练习题里吧，对于新手来讲还是挺有意义的。...

2018-02-27

0 346