Browse Category

动态规划

POJ 1159 Palindrome （LCS）

给出一个字符串，问最少添加几个字符才能构成一个回文串。

勇太有一棵 n 个节点的以1为根的有根树。现在他可以对这棵树进行若干次操作，每一次操作可以选择树上的一个点然后删掉这个点和它的儿子之间的所有边。

现在勇太想要知道对于每一个 k ∈ [1, n]，最少需要多少次操作才能让图中恰好存在 k 个联通块。

有一个迷宫r行c列，开始在 [1,1] ，现在要走到 [r,c] ，在点 [x,y] 处我们有 P0 的概率保持原地不动，有 P1 的概率走到 [x][y+1] ，有 P2 的概率走到 [x+1][y] ，每次消耗2点魔力，求平均消耗多少魔力能走到 [r,c] 。

在你的童年有过收集零食里面的卡片的经历吧！当你集得所有卡片的时候你会获得很多奖励。

输入的第一行代表需要集得卡片的数量N，接下来的一行有N个实数，代表每张卡片出现的概率，问最少需要买多少零食才可以集全所有卡片。

给出两个字符串，每次我们可以把一个字符串的一个区间刷成同一个字母，问最少多少步可以把第一个字符串变为第二个字符串

给定一个数n，求[1,n]中含有”49″的数的个数。