CodeForces 660E – Different Subsets For All Tuples [DP]


Link 传送门 Problem For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including the empty subsequence). You are given two positive integers n and m. Let S be the set of all sequenc...

CodeForces 660E – Different Subsets For All Tuples [DP]

Link 传送门 Problem For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including ...
阅读全文 0

HDU 2089 – 不要62 [数位DP]


Link 传送门 Problem 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。 不吉利的数字为...

HDU 2089 – 不要62 [数位DP]

Link 传送门 Problem 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含...
阅读全文 0

HDU 1158 – Employment Planning [DP]


Link 传送门 Problem A project manager wants to determine the number of the workers needed in every month. He does know the minimal number of the workers needed in each month. When he hires or fires a worker, there will be some extra cost. Once a w...

HDU 1158 – Employment Planning [DP]

Link 传送门 Problem A project manager wants to determine the number of the workers needed in every month. He does know the minimal number of the wo...
阅读全文 0

HDU 5642 – King’s Order [数位DP]


Link 传送门 Problem After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to time. But sometimes he can not speak things well. So in his order there are some ones like this: “...

HDU 5642 – King’s Order [数位DP]

Link 传送门 Problem After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to tim...
阅读全文 0

POJ 2151 – Check the difficulty of problems [概率DP]


Link 传送门 Problem Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms: 1. All of the teams solve at least one problem. 2...

POJ 2151 – Check the difficulty of problems [概率DP]

Link 传送门 Problem Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect t...
阅读全文 0

UVa 1424 – Salesmen [DP]


Link 传送门 Mean 给定一个N个点M条边的无向图,一个人走出了一个路径,但这个路径有可能是不对的,例如图上并没有某条边。给你这个路径,让你再找出一条等长的路径,使得两条路径的距离最近。 路径的距离定义如下:每个点相同为0,不同为1. Analysis 比较简单的dp,...

UVa 1424 – Salesmen [DP]

Link 传送门 Mean 给定一个N个点M条边的无向图,一个人走出了一个路径,但这个路径有可能是不对的,例如图上并没有某条边。给你这个路径,让你再找出一条等长...
阅读全文 0

UVa 11552 – Fewest Flops [DP]


Link 传送门 Problem A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the character itself. For example, the string “aabbbaabaaaa” ma...

UVa 11552 – Fewest Flops [DP]

Link 传送门 Problem A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of ti...
阅读全文 0

ZOJ 2341 – Quantization Problem [记忆化搜索+打印路径]


LInk 点击打开zoj题目链接 Problem When entering some analog data into a computer, this information must be quantized. Quantization transforms each measured value x to some other value l(x) selected from the predefined set L of levels. Sometimes to ...

ZOJ 2341 – Quantization Problem [记忆化搜索+打印路径]

LInk 点击打开zoj题目链接 Problem When entering some analog data into a computer, this information must be quantized. Quantization transforms each m...
阅读全文 0

HDU 5115 – Dire Wolf [区间DP]


点击打开HDU题目链接 题意 给你N个怪物,知道他们的原始攻击力和附加攻击力,附加攻击力是指对左右旁边的帮助攻击力。问你杀掉所有的怪物最少需要花费多少总力量 分析 比赛的时候没想到是DP啊,以为已经有个DP了不可能还有一个,果然还是自己太水了。这道题区间DP对...

HDU 5115 – Dire Wolf [区间DP]

点击打开HDU题目链接 题意 给你N个怪物,知道他们的原始攻击力和附加攻击力,附加攻击力是指对左右旁边的帮助攻击力。问你杀掉所有的怪物最少需要花费多少总...
阅读全文 0

HDU 5418 – Victor and World [状态压缩DP]


点击打开HDU题目链接 题意 类似于可以重复走的旅行商问题,从起点1开始走编所有点,最后回到起点。 分析 因为节点不多,先用`floyd`求出最短路,然后用DP状态压缩求出来 官方题解 部分人可能对这道题的题面有点熟悉,其实这道题的标题本来叫做Victor and Around the ...

HDU 5418 – Victor and World [状态压缩DP]

点击打开HDU题目链接 题意 类似于可以重复走的旅行商问题,从起点1开始走编所有点,最后回到起点。 分析 因为节点不多,先用`floyd`求出最短路,然后用DP状态...
阅读全文 0