UVA 5875 DP
uva--562Dividing coins +dp
题意： 给定一堆硬币，然后将他们分成两部分，使得两部分的差值最小;输出这个最小的差值。 思路： 想了好久都没想到一个合适的状态转移方程。后面看了别人的题解后，才知道能够转成背包问题求解。 我们将全部的硬币和的一半作为背包容量，然后将硬币的代价看成其本身的面值。然后背包中能装的最大容量 就是当中一个人分得硬币数。 代码例如以下
日期 2023-06-12 10:48:40
uva 1331 - Minimax Triangulation(dp)
题目链接：uva 1331 - Minimax Triangulation 题目大意：依照顺时针或者逆时针的顺序给出多边的点，要将这个多边形分解成n-2个三角形，要求使得这些三角行中面积最大的三角形面积尽量小，求最小值。 解题思路：状态非常好想。dp[i][j]表示从第i个点到第j个点，划分成j-i-1个三角形的最优解，然后每次转移时，枚举长度和左边界始点，那么依据长度和左边界点就
日期 2023-06-12 10:48:40
UVA 1358 - Generator(dp+高斯消元+KMP)
UVA 1358 - Generator 题目链接 题意：有m种字符（从'A'開始往后数的大写字母)，如今有一个字符串，长度不超过12。如今每次随机生成一个字母，要求能产生该字符串的期望长度 思路：dp[i]表示产生长度i的期望长度，那么每次产生一个字符。相应m种转移，每种转移的概率为1/m,转移后的长度能够利用KMP的next数组去高速获得，然后因为转移可能形成环的情况，所以无法直
日期 2023-06-12 10:48:40UVA 1484 - Alice and Bob's Trip（树形DP）
题目链接：1484 - Alice and Bob's Trip 题意：BOB和ALICE这对狗男女在一颗树上走，BOB先走，BOB要尽量使得总路径权和大，ALICE要小，可是有个条件，就是路径权值总和必须在[L,R]之间，求终于这条路径的权值。 思路：树形dp，dp[u]表示在u结点的权值，往下dfs的时候顺带记录下到根节点的权值总和，然后假设dp[v] + w + sum 在[l,r]
日期 2023-06-12 10:48:40uva The Tower of Babylon[LIS][dp]
转自：https://mp.weixin.qq.com/s/oZVj8lxJH6ZqL4sGCXuxMw The Tower of Babylon（巴比伦塔） Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. S
日期 2023-06-12 10:48:40
UVaLive 3490 Generator (KMP + DP + Gauss)
题意：随机字母组成一个串，有一个目标串，当这个由随机字母组成的串出现目标串就停止，求这个随机字母组成串的期望长度。 析：由于只要包含目标串就可以停止，所以可以先把这个串进行处理，也就是KMP，然后dp[i] 表示从 i 结点到完全匹配期望长度，所以很容易得到状态转移方程 dp[i] = ∑dp[j] / n + 1，然后用高斯消元即可，要注意，要用全整数的高斯消元。 代码如下： #p
日期 2023-06-12 10:48:40
UVa 11367 Full Tank? (DP + Dijkstra)
题意：n个城市有m条道路。每个城市的油价不一样，给出起点s和终点t，以及汽车的油箱的容量，求从城市s到城市 t 的最便宜路径。 析：dp[u][i] 表示在第 u 个城市，还剩下 i L升油，一开始用BFS，TLE，要注意效率，用dijkstra，找到城市 t 就该结束了。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000"
日期 2023-06-12 10:48:40UVa 10269 Adventure of Super Mario (Floyd + DP + BFS)
题意：有A个村庄，B个城市，m条边，从起点到终点，找一条最短路径。但是，有一种工具可以使人不费力的移动L个长度，但始末点必须是城市或村庄。这种工具有k个，每个只能使用一次，并且在城市内部不可使用，但在村庄内部可使用。另外，在城市或村庄内部的时间不计。 析：先预处理出来使用工具能到达的距离，这个可以用Floyd 来解决，然后f[i][u] 表示到达 u 还剩下 i 次工具未用，然后用bfs就可以很
日期 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:40UVa 11468 Substring (AC自动机+概率DP)
题意：给出一个字母表以及每个字母出现的概率。再给出一些模板串S。从字母表中每次随机拿出一个字母，一共拿L次组成一个产度为L的串， 问这个串不包含S中任何一个串的概率为多少？ 析：先构造一个AC自动机，然后随机生成L个字母，就是在AC自动机的某个结点走多少步，dp[i][j] 表示在 i 结点，并且剩下 j 步， 然后记忆化搜索就OK了。 代码如下： #pragma comment(linker
日期 2023-06-12 10:48:40UVa 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 10859 Placing Lampposts (树形DP)
题意：给定一个无向无环图，要在一些顶点上放灯使得每条边都能被照亮，问灯的最少数，并且被两盏灯照亮边数尽量多。 析：其实就是一个森林，由于是独立的，所以我们可以单独来看每棵树，dp[i][0] 表示不在 i 点放灯，dp[i][1] 表示在 i 点放灯，很简单的一个DP 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #
日期 2023-06-12 10:48:40UVaLive 7143 Room Assignment (组合数+DP)
题意：有 n 个客人，m个房间，每个房间可住ci个人，这 n 个人中有 t 对双胞胎，sum{ci} = n 问你有多少种住房方法。 析：计数DP，dp[i][j] 表示前 i 个房间，还剩下 j 对双胞胎未住，第 i+1 个房间，就从剩下的 j 对双胞胎中选 k 对，然后再从不是双胞胎的人选剩下的，每对先选一个，然后再从剩下的选全部的， 求组合数过程可能要用到逆元，可以提前打表。
日期 2023-06-12 10:48:40UVa 1336 Fixing the Great Wall (区间DP)
题意：给定 n 个结点，表示要修复的点，然后机器人每秒以 v 的速度移动，初始位置在 x，然后修复结点时不花费时间，但是如果有的结点暂时没修复， 那么每秒它的费用都会增加 d，修复要花费 c，坐标是 pos，问你最少花费是多少。 析：dp[i][j][k] 表示已经修复了 i-j 区间，并且当前在 k，那么两种方案，向左移动，或者向右移动，最后输出就好了。 代码如下： #pragma comm
日期 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 1631 Locker (DP)
题意：有一个 n 位密码锁，每位都是0-9，可以循环旋转。同时可以让1-3个相邻数字进行旋转一个，给定初始状态和目状态，问你最少要转多少次。 析：很明显的一个DP题。dp[i][j][k] 表示前 i 位已经转好，并且第 i+1 位是 j ，第 i+2 位是 k，那么我们先把第 i 位转到指定位置，然后计算转多少次， 然后再考虑 i+1位和 i+2位，要旋转小于等于第 i 位的次数，这就转移完了
日期 2023-06-12 10:48:40UVaLive 6697 Homework Evaluation (DP)
题意：给出一个长字符串，再给一个短字符串，进行匹配，如果第i个恰好匹配，则 +8,；如果不匹配，可以给长或短字符串添加-，先后匹配，这样-3， 连续的长字符串添加-，需要减去一个4；也可不给添加-，则-5。 析：dp[i][j][0] 表示第一个字符串第 i 个位置，和第二个字符串的第 j 个位置相匹配，dp[i][j][1] 表示第一个字符串第 i 个位置，和第二个字符串的第 j 个位置加_相
日期 2023-06-12 10:48:40
UVa 1630 Folding (区间DP)
题意：折叠一个字符串，使得其成为一个尽量短的字符串 例如AAAAAA变成6（A） 而且这个折叠是可以嵌套的，例如 NEEEEERYESYESYESNEEEEERYESYESYES 会变成 2(N5(E)R3(YES))。 析：用dp[i][j] 表示字符串中的第 i 个到第 j 个字符压缩后的最短长度。那么就有两种方式，一种就是自身压缩都最短，另一种就是两段分别压缩， 然后
日期 2023-06-12 10:48:40UVaLive 6625 Diagrams & Tableaux (状压DP 或者 DFS暴力)
题意：给一个的格子图，有 n 行单元格，每行有a[i]个格子，要求往格子中填1~m的数字，要求每个数字大于等于左边的数字，大于上边的数字，问有多少种填充方法。 析：感觉像个DP，但是不会啊。。。就想暴力试试，反正数据量看起来不大才7，但是。。。TLE了，又换了一个暴力方法，2秒多过了，差点啊。 其实这是一个状压DP，dp[i][s]表示在第 i 列，在集合 s 中有方法数，那么怎么转移呢，这个还
日期 2023-06-12 10:48:40UVa 10817 Headmaster's Headache (状压DP+记忆化搜索)
题意：一共有s(s ≤ 8)门课程，有m个在职教师，n个求职教师。每个教师有各自的工资要求，还有他能教授的课程，可以是一门或者多门。 要求在职教师不能辞退，问如何录用应聘者，才能使得每门课只少有两个老师教而且使得总工资最少。 析：用两个集合来表示状态，s1表示恰好有一个人教的科目，s2表示至少有两个人能教的科目。d(i, s1, s2),表示已经考虑了前 i 个人的最少花费。 这里把所有的人和科
日期 2023-06-12 10:48:40UVa 10900 So you want to be a 2n-aire? （概率DP，数学）
题意：一 个答题赢奖金的问题，玩家初始的金额为1，给出n，表示有n道题目，t表示说答对一道题目的概率在t到1之间，每次面对一道题，可以选择结束游戏， 获得当 前奖金；回答下一道问题，答对的概率p在t到1之间，答对的话奖金翻倍，答错的话结束游戏，没有奖金，求玩家赢的奖金的期望值的最大值。 析：首先是求期望，那就和平均值差不多，我们来分析第 i 道题时，两个情况，要么回答，要么不回答，如果不回答那么
日期 2023-06-12 10:48:40UVa 1025 A Spy in the Metro （DP动态规划）
题意：一个间谍要从第一个车站到第n个车站去会见另一个，在是期间有n个车站，有来回的车站，让你在时间T内时到达n，并且等车时间最短， 也就是尽量多坐车，最后输出最少等待时间。 析：这个挺复杂，首先时间是一个顺序，设d（i，j）表示时刻 i 在第 j 个车站，最少还要等待多长时间，那么边界是d(T, n) = 0。 并且有三种决策： 决策一：等着 d[i][j] = d[i + 1][j] + 1;
日期 2023-06-12 10:48:40UVa 1220 Party at Hali-Bula （树形DP，最大独立集）
题意：公司有 n 个人形成一个树形结构，除了老板都有唯一的一个直系上司，要求选尽量多的人，但不能同时选一人上和他的直系上司，问最多能选多少人，并且是不是唯一的方案。 析：这个题几乎就是树的最大的独立集问题，只不过多一个判断唯一性而已。用两个数组，一个用来记录人数，一个用来判断唯一性。 d[u][0]，表示以 u 为根的子树中，不选 u 点能够得到最大人数，那么d[u][1]就是选 u 点能达到最
日期 2023-06-12 10:48:40UVa 12186 Another Crisis （DP）
题意：有一个老板和n个员工，除了老板每个员工都有唯一的上司，老板编号为0，员工们为1-n，工人（没有下属的员工），要交一份请愿书， 但是不能跨级，当一个不是工人的员工接受到直系下属不少于T%的签字时，自己也会签字，并交给上级，问你最少有多少工人签字，才能让老板收到请愿书。 析：题意比较简单，也好理解，很明显是一个动态规划的题目，d(u)表示u给上级要发信至少需要多少工人签字。假设u有k个结点，那
日期 2023-06-12 10:48:40UVa 111 History Grading （简单DP，LIS或LCS）
题意：题意就是坑，看不大懂么，结果就做不对，如果看懂了就so easy了，给定n个事件，注意的是， 它给的是第i个事件发生在第多少位，并不是像我们想的，第i位是哪个事件，举个例子吧，4 2 3 1， 表示的是第一个事件发生在第四，第二个事件发生在第二位，第三个在第三位，第四个在第一位。 然后输入n个答案，求有多少个事件相对位置是和原来一样的。 那么知道输入好办了，我们只需对输入做一下预处理，就变
日期 2023-06-12 10:48:40uva 104 Arbitrage （DP + floyd）
uva 104 Arbitrage Description Download as PDF Background The use of computers in the finance industry has been marked with controversy lately as programmed trading – designed to take adv
日期 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:40UVA 11578 - Situp Benches（dp)
题目链接：11578 - Situp Benches 题意：健♂身♂房有两个仰卧起坐坐垫，每次调整角度要花费10元/10度，每次使用要花费15，如今给定n个人的时间顺序，和所希望的角度，求最少花费 思路：dp，dp[i][j][k]表示第i个人，一个角度为j,还有一个为k的最小花费，一个人用和两个人用的情况分开讨论，然后记录dp状态转移路径。这个输出路径让这题变得麻烦了不少。只是机智的我还
日期 2023-06-12 10:48:40