[综合] UVa 116 Unidirectional TSP (多段图的最短路 DP)

阶段很明显即走到第几列; 状态：走到第i列j行，d[i][j]表示至少还要经过的整数，便是求d[i]中的最小解; 决策：三种走法; 决策选择：选d[i][j]最小的那个 #include<iostream> #include<cstdio> #include<alg...

[综合] UVa 12563 Jin Ge Jin Qu hao(DP 多种状态表示）

状态A 状态：d[i][j]已经第i首歌还剩j时间，还能最多唱几首决策：唱或不唱1)d[i][j]-->d[i+1][j-song[i]]; 2)d[i][j]-->d[i+1][j]; 选择：最大的但j>0的 intdp(inti,intj) {int&ans=d[i]...

[综合] 最长上升子序列(LIS DP)

状态：d[i]表示以i结尾的最长上升子序列 状态转移：d(i)=max{0,d(j)|j<i,Aj<Ai}+1; 当A[i]>A[j]说明又多了个子序列+1; constintmaxn=1000+5; intmain() {intn,s[maxn],d[maxn]={0};sca...

[综合] 最长公共子序列（LCS DP）

状态：d[i][j]，i，j表示下标，A[1~i]和B[1~j]的最长LCS 状态转移：d[i][j]-->1)A[i]==B[j]d[i][j]=d[i-1][j-1]+1; 2)A[i]!=B[j]d[i][j]=max(d[i-1][j],d[i][j-1]); constintma...

[综合] DNA比对(DP)

【编程题】(满分27分) 脱氧核糖核酸即常说的DNA，是一类带有遗传信息的生物大分子。它由4种主要的脱氧核苷酸(dAMP、dGMP、dCMT和dTMP)通过磷酸二酯键连接而成。这4种核苷酸可以分别记为：A、G、C、T。 DNA携带的遗传信息可以用形如：AGGTCGACTCCA....的串来表示。...

[综合] 居民集会(分治法）

标题：居民集会 蓝桥村的居民都生活在一条公路的边上，公路的长度为L，每户家庭的位置都用这户家庭到公路的起点的距离来计算，第i户家庭距起点的距离为di。 每年，蓝桥村都要举行一次集会。今年，由于村里的人口太多，村委会决定要在4个地方举行集会，其中3个位于公路中间，1个位最公路的终点。 已知...

[综合] 畅通工程(DFS求连通块)

要求最少多少个点才能连所有边 思路：如果1与2相连，就把1和2看成一个点，即所有连通的点整体看成一个点; 那么连通n个点至少需要n-1条边 #include<iostream> #include<cstdio> #include<cstring> usingna...

[综合] UVA 11582 Colossal Fibonacci Numbers!

原则1：n的余数最多有n种，所以最多n^2就会一个循环，就像400前后同一天的星期几也一样，是个至少要满足的循环 n是1~1000，f函数从第3项开始算时间超出，所以直接打表 #include<iostream> #include<cstdio> #include<s...

[综合] UVA 1635 Irrelevant Elements

看到一个很大的数字的什么什么的余数就要想到唯一分解定律 #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #inc...

[综合] 小于n且与n互素的整数个数(欧拉函数)的计算

即计算1~n中与n互素的整数个数 互素就是无法被n整除的数（"与p互素"和"不是p的倍数"是等价的） 所以第一种显而易见的方法就是暴力枚举法，但效率太低。 第二种方法用唯一分解定律再运用容斥原理： 分解定律：分为n=p1^a1*p2^a2......pk^ak; 容斥原理：在计数时，要保证无一重...

[综合] UVA 1637 Double Patience(DP+概率)

一共9堆牌，每堆牌有0~4这5种状态，所以一共有5^9=1953125种 状态定义：对于状态i，d[i]表示在这种状态下要成功的概率，也即是后序状态成功几率的平均值(因为每种状态选取的几率一样) 状态转移：也即是1)拿这两对相同的牌2)拿下一对相同的牌 状态选取：因为是计算总的成功的概率所以不存在...

[综合] UVA 580 Critical Mass(递推)

递推思想就是把这一项递推到前一项，把问题简单化，例如Fibonacci数列f(n)=f(n-1)+f(n-2) 题目的意思就是n个长度字符中至少有3个连续的U的字符有几种 于是问题核心就是怎么递推，使问题规模减少 假设答案为f(n)，从第一个连续的U开始编号为第i,i+1,i+2个 于是字符串...

[综合] UVA 12034 Race

递推 假设第一名有i人，即C(n,i)i∈[1,n]，剩下n-i个人的名次有f(n-i)种可能性，只要对于每种排名，将i个人都放在并列第一就是一种新的排名 所以f(n)=∑f(n-1)*C(n,i); 对于这i个人不需要考虑剩下如处于第二第三的情况，因为f(n-i)中已经包含这种情况了 剩下就是计...

[综合] UVA 1638 Pole Arrangement

如果考虑l代表右边比他高的有几个，r代表左边高的有几个，l代表右边高的有几个那么会超级复杂，排列约束条件很多 只能考虑有序化方便决策：从最矮开始排每增加一个会遮住很多柱子，没什么规律 所以考虑从最大开始排， 每插入一根会导致三种结果 1）插到左边使r+1只有一种插法 2）插到右边使l+1只有一种插...

[综合] UVA 437 The Tower of Babylon

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<vector> #include&l...

[综合] UVA 1626 Brackets sequence

状态表示：d(i,j)表示i~j至少要添加几个括号 状态转移：1）(S)或[S]转移成S，即d(i,j)-->d(i+1,j-1)如果s[i]==s[j] 2）A=S1+S2转移成S1和S2，即d(i,j0-->d(i,k)+d(k+1,j) 但每种都要转移到第二种方法试一试，如[][]...

[综合] UVA 12186 Another Crisis

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #includ...

[综合] UVA 1220 Party at Hali-Bula(树的最大独立集)

树的独立集：即集合中任选两个点互相不相邻，互相不构成父子关系。且其中最大的集合即为最大独立集 状态定义：1）d(u,1)，f(u,1)表示选u点情况下，在u的子树中，能得到的最大人数以及方案的唯一性 2）d(u,0)，f(u,0)表示不选u点情况下，在u的子树中，能得到的最大人数以及方案的唯一性 状...

[综合] 百练 4155 鸣人和佐助

百练4155 #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<algorithm>...

[综合] 百练 4116 拯救行动

4116:拯救行动 #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<algorit...