Ural « Beyond the Void

Ural 1416 Confidential

第一问是求最小生成树，第二问是求次小生成树。如果次小生成树不存在（本身就是一棵树），则输出-1。

...

题目大意是给定N个垃圾桶，每个垃圾桶内装有N种数量不同的垃圾，现你把垃圾分类，要求每个垃圾桶装一种垃圾，移动一个单位的垃圾消耗1的代价，求最小的移动代价，使得完成垃圾分类...

括号序列问题，刘汝佳黑书上的动态规划第一题，真是经典问题。不过这道题要输出方案。

动态规划状态设定
F[i,j]表示子序列[i,j]要成为括号序列所需添加的最小括号数目。

...

动态规划，由于是马进入马厩连续的，要先预处理求出每个连续序列的马进入一个马厩的不快乐值。然后以O(N^2*K)时间复杂度DP。

设A[0][i]为前i匹马中种类为0的马的数量，A[1][i]为前i匹马...

==1102==
对于读入的每一行分别进行动态规划。

状态
F[i]前i为是否可以连续达到

状态转移方程
F[i]= or { F[i-Len[j] | i-Len[j]>=0 并且 S[i-Len[j]+1] 匹配 W[j] }

边界条件
...

==1031==

动态规划，设定F[i]为到达第i个城市的最小花费，从第S个城市开始，到第T个城市结束

注意有可能S

...

==1002==
首先把单词按照规则替换为数字序列，构图，把电话号码的每一位作为一个顶点。增加一个0号顶点。

如果一个单词的数字序列能够匹配电话号码的A到B位，那么我们就在第A-1...