uva 1291(dp)
UVa 12683 Odd and Even Zeroes（数论+数字DP）
意甲冠军： 要求 小于或等于n号码 （0<=n <= 1e18）尾数的数的阶乘0数为偶数 思考：当然不是暴力，因此，从数论。尾数0数为偶数，然后，它将使N阶乘5电源是偶数。（二指数肯定少5指数），乞讨N。阶乘5该指数是N/5+ N/25+N/125。。。。 以530为例。尝试着将转化为5进制 即为 4110。那么5的指数 就是 411+41+4 （5进制）easy发现
日期 2023-06-12 10:48:40
UVa 11427 Expect the Expected (数学期望 + 概率DP)
题意：某个人每天晚上都玩游戏，如果第一次就䊨了就高兴的去睡觉了，否则就继续直到赢的局数的比例严格大于 p，并且他每局获胜的概率也是 p，但是你最玩 n 局，但是如果比例一直超不过 p 的话，你将不高兴的去睡觉，并且以后再也不玩了，现在问你，平均情况下他玩几个晚上游戏。 析：先假设第一天晚上就不高兴的去睡觉的概率是 q，那么有期望公式可以得到 E = q + (1-q) * (E + 1)，其中
日期 2023-06-12 10:48:40UVa 11021 Tribles (概率DP + 组合数学)
题意：有 k 只小鸟，每只都只能活一天，但是每只都可以生出一些新的小鸟，生出 i 个小鸟的概率是 Pi，问你 m 天所有的小鸟都死亡的概率是多少。 析：先考虑只有一只小鸟，dp[i] 表示 i 天全部死亡的概率，那么 dpi] = P0 + P1*dp[i-1] + P2*dp[i-1]^2 + ... + Pn*dp[i-1]^(n-1)，式子 Pjdp[i-1]^j 表示该小鸟生了 j 后代
日期 2023-06-12 10:48:40UVaLive 3490 Generator (KMP + DP + Gauss)
题意：随机字母组成一个串，有一个目标串，当这个由随机字母组成的串出现目标串就停止，求这个随机字母组成串的期望长度。 析：由于只要包含目标串就可以停止，所以可以先把这个串进行处理，也就是KMP，然后dp[i] 表示从 i 结点到完全匹配期望长度，所以很容易得到状态转移方程 dp[i] = ∑dp[j] / n + 1，然后用高斯消元即可，要注意，要用全整数的高斯消元。 代码如下： #p
日期 2023-06-12 10:48:40
UVa 11324 The Largest Clique (强连通分量+DP)
题意：给定一个有向图，求一个最大的结点集，使得任意两个结点，要么 u 能到 v，要么 v 到u。 析：首先，如果是同一个连通分量，那么要么全选，要么全不选，然后我们就可以先把强连通分量先求出来，然后缩成一个点，然后该图就成了一个DAG，然后就可以直接用DP来做了。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #in
日期 2023-06-12 10:48:40UVa 1204 Fun Game (状压DP)
题意：有一些小孩（至少两个）围成一圈，有 n 轮游戏，每一轮从某个小孩开始往左或者往右伟手帕，拿到手帕写上自己的性别（B，G），然后以后相同方向给下一个。 然后在某个小孩结束，给出 n 轮手帕上的序列，求最少有多少个小孩。 析：很容易知道是状压DP，也很容易写出状态方程，dp[s][i][j] 表示 已经选择了 s 的手帕，然后第一个是 i，最后一个是 j，然后再转移，很简单，但是， 这样时间复
日期 2023-06-12 10:48:40
UVa 10564 Paths through the Hourglass (DP)
题意：从最上面走到最下面，使得路过的数求和为s，并输出编号最小的一组路径。 析：基本动规，dp[i][j][s] 从最下面到 i，j 和为s，路径数，要么从左面要么从右，求和就好了，注意上面和下面的不太一样，要分别求解。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #
日期 2023-06-12 10:48:40UVaLive 3530 Martian Mining (简单DP)
题意：给定一个n*m的网格，每个格子里有A矿和B矿数量，A必须由右向左运，B只能从下向上运，中间不能间断，问最大总数量。 析：一个简单DP，dp[i][j] 表示 从 （0， 0） 到 （i， j） 最大人运输量。要么向左运输，要么向上运输，取最大值。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include
日期 2023-06-12 10:48:40
UVa 11552 Fewest Flops (DP)
题意：给一个字符串，把它分为ｋ块，每一块里面的字母可以任意的排序。最终字符串， 连续的一样的字母算作一个chunk，问总chunks最少是多少？ 析：dp[i][j] 表示第 i 个块，第 j 位在末尾时chunk最少，状态转移方程也应该好写，如果 dp[i-1][j] 和第 i 块第一个一样，那么就总数就会-1， 否则就是直接加上。 代码如下： #pragma comment(
日期 2023-06-12 10:48:40UVaLive 3983 Robotruck (DP + 单调队列)
题意：有n个垃圾，第i个垃圾坐标为(xi,yi)，重量为wi，有一个机器人，要按照编号从小到大的顺序剑气所有的垃圾兵扔进垃圾桶，垃圾桶在原点， 每次总重量不能超过C,两点间距离为曼哈顿距离，求出最短的距离和。 析：第一反应想到的状态是有个数和重量，一看，时间复杂度受不了，只能改。dp[i] 表示从原点出发倒掉前 i 个垃圾，并放到垃圾桶所要的最短距离。 dp[i] = min{dp[j] + d
日期 2023-06-12 10:48:40UVaLive 10859 Placing Lampposts (树形DP)
题意：给定一个无向无环图，要在一些顶点上放灯使得每条边都能被照亮，问灯的最少数，并且被两盏灯照亮边数尽量多。 析：其实就是一个森林，由于是独立的，所以我们可以单独来看每棵树，dp[i][0] 表示不在 i 点放灯，dp[i][1] 表示在 i 点放灯，很简单的一个DP 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #
日期 2023-06-12 10:48:40UVa 10891 Game of Sum (DP)
题意：给定一个长度为n的整数序列，两个人轮流从左端或者右端拿数，A先取，问最后A的得分-B的得分的结果。 析：dp[i][j] 表示序列 i~j 时先手得分的最大值，然后两种决策，要么从左端拿，要么从右端拿，肯定是拿的是最大的。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio&g
日期 2023-06-12 10:48:40
UVa 11584 Partitioning by Palindromes (简单DP)
题意：给定一个字符串，求出它最少可分成几个回文串。 析：dp[i] 表示前 i 个字符最少可分成几个回文串，dp[i] = min{ 1 + dp[j-1] | j-i是回文}。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string>
日期 2023-06-12 10:48:40UVaLive 6680 Join the Conversation (DP)
题意：给出n条发言，让你求最大的交流长度并输出标记顺序。 析：这个题要知道的是，前面的人是不能at后面的人，只能由后面的人at前面的，那就简单了，我们只要更新每一层的最大值就好，并不会影响到其他层。 最后再从这 n 层中取出最大值，在更新时，也可以记录着最大值。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #inc
日期 2023-06-12 10:48:40UVa 242 Stamps and Envelope Size (无限背包，DP)
题意：信封上最多贴S张邮票。有N个邮票集合，每个集合有不同的面值。问哪个集合的最大连续邮资最 大，输出最大连续邮资和集合元素。 最大连续邮资是用S张以内邮票面值凑1，2，3...到n+1凑不出来了，最大连续邮资就是n。如果不止一个集合结果相 同，输出集合元素少的， 如果仍相同，输出最大面值小的。 析：这个题，紫书上写的不全，而且错了好几次，结果WA好几次。 首先这个和背包问题差不多，我们只用一维
日期 2023-06-12 10:48:40UVa 10723 Cyborg Genes (LCS, DP)
题意：给定两行字符串，让你找出一个最短的序列，使得这两个字符串是它的子串，并且求出有多少种。 析：这个题和LCS很像，我们就可以利用这个思想，首先是求最短的长度，不就是两个字符串长度之和再减去公共的么。那么有多少种呢？ 同样也是分两种情况讨论，如果s1[i-1] == s2[j-1] 那么种类数肯定和 ans[i-1][j-1]一样了，没有变化，再就是如果不相等怎么算呢？ 难道也是ans[i][
日期 2023-06-12 10:48:40UVa 1630 Folding (区间DP)
题意：折叠一个字符串，使得其成为一个尽量短的字符串 例如AAAAAA变成6（A） 而且这个折叠是可以嵌套的，例如 NEEEEERYESYESYESNEEEEERYESYESYES 会变成 2(N5(E)R3(YES))。 析：用dp[i][j] 表示字符串中的第 i 个到第 j 个字符压缩后的最短长度。那么就有两种方式，一种就是自身压缩都最短，另一种就是两段分别压缩， 然后
日期 2023-06-12 10:48:40UVa 1638 Pole Arrangement (递推或DP)
题意：有高为1，2，3...n的杆子各一根排成一行，从左边能看到L根，从右边能看到R根，求杆子的排列有多少种可能。 析：设d（i, j, k）表示高度为1-i的杆子排成一行，从左边看到j根，从右边看到k根的数目。当i>1时，我们按照从大到小的顺序按排杆子， 假设已经安排完i-1根了，那么还剩下一根就是高度为1的了，那么它放在哪都不会挡住任何一根杆子。情况有3种： 1.放在左边，那么在左边一
日期 2023-06-12 10:48:40LA 3942 && UVa 1401 Remember the Word (Trie + DP)
题意：给你一个由s个不同单词组成的字典和一个长字符串L，让你把这个长字符串分解成若干个单词连接（单词是可以重复使用的），求有多少种。（算法入门训练指南-P209） 析：我个去，一看这不是一个DP吗？刚开始交一直是runtime error，找了好久，一直以为是数组开小了，不断增大还是这样，后来发现我用了char类型。。。下面分析这个题目 应该不难想到这个状态转移方程： d(i) = sum{d(
日期 2023-06-12 10:48:40UVa 10534 Wavio Sequence (最长递增子序列 DP 二分)
Wavio Sequence Wavio is a sequence of integers. It has some interesting properties. · Wavio is of odd length i.e. L = 2*n + 1. · The first (n+1) integer
日期 2023-06-12 10:48:40