Codeforces DP 第二弹

比赛链接  代码全在里面 

打*的算是好题吧

	1 / 1	Problem A	CodeForces 61D	Eternal Victory
	1 / 3	Problem B	CodeForces 67A	Partial Teacher
	1 / 3	Problem C	CodeForces 148E	Porcelain
	1 / 1	Problem D	CodeForces 79C	Beaver
	1 / 4	Problem E	CodeForces 222E	Decoding Genome
	1 / 3	Problem F	CodeForces 107B	Basketball Team
	1 / 2	Problem G	CodeForces 174B	File List
	1 / 2	Problem H	CodeForces 10B	Cinema Cashier
	1 / 3	Problem I	CodeForces 208C	Police Station
	1 / 2	Problem J	CodeForces 82D	Two out of Three

A 最基本的树dp模型

B 算是一个小递推，要考虑怎么最优

C* 题意: 一个n层的书架(n=100)，每层有a[i]本书，每本书有各自的价值，

   每次拿书只能拿某一层两边的书，问你拿m本书能获得的最大价值

   做法: 预处理出第i层 取j本书所能获得的最大价值(枚举i,j, 再枚举左边取k本,  

   之前还要预处理左边的前缀和，和右边的后缀和)， 然后用一个背包处理

   (枚举第i层，枚举书的总数j，枚举这一层要拿的书本数k)即可

D  two points   当你枚举到子串的末端，你要将指针跳到距离当前最长的合法位置，

    这个合法位置用数组预处理出来

E  AC自动机+矩阵乘法 退化的一个题， 这里只需要矩阵乘法就可以了

F 简单数学题，组合数计算一下

G字符串乱搞题

H *dp[i][j][k]表示取了从(i,j) ----(i,k) 后所有点与中心的距离和，  可以根据dp[i][j][k-1]推过来

   对于每个询问，给你长度val, 枚举行i列j找出最小值去放， 放好以后注意 把一些不能取的dp更新掉

   这里我更新成了-1表示不存在，不能取的dp肯定是包含已经取过的点，这个可以O(n^2)维护

I *题意自己看一下吧，显然答案至少是1.000000(取点1或取点n)，假如最短路上有除了1，n点以外的点可以选，

 那么没选一个点，对于一条最短路可以覆盖2条边， 所以我们要找一个点让他覆盖的最短路的个数最多，

 我们用cnt[i][j]表示i到j的最短路条数， 对于一个点i它能覆盖cnt[1][i]*cnt[i][n]*2.0条边，

 那么答案就是cnt[1][i]*cnt[i][n]*2.0/cnt[1][n]的最大值, cnt数组的求法明显的floyd嘛

J*题意:超市排队付钱， 每次从队伍前3个人里面选2个一个处理，费用为2个权值的最大值，

   当人数为一个时单独处理，并输出解， 人的下标从0开始。

    dp[i][j]表示选到第i个(第i个已经被拿掉) 前面只剩j的最小费用，然后dp[n][n]就是答案

Codeforces DP 第二弹,布布扣,bubuko.com

Codeforces DP 第二弹

原文：http://blog.csdn.net/auto_ac/article/details/22685473