Dynamic Programming Exercises Beginner 归档题解(2)
2016-02-13
归档地址 再来10题！
题目 UVa 10817 - Headmaster's Headache 由于每个申请者可选可不选，所以就像一个 01 背包一样。用上一篇定状态的方法，对后面决策的影响就只有现在剩余哪些课没人教。所以定义状态： d p [ i ] [ s ] dp[i][s] d p [ i ] [ s ]......
UVa 10453 - Make Palindrome
2016-02-10
题目地址
描述 给定一个长度为 n ( n ≤ 1 0 0 0 ) n(n\le 1000) n ( n ≤ 1 0 0 0 ) 的字符串，你需要在任意位置添加尽量少的字符，使新串是回文串。输出最少添加的字符个数以及新串。
样例输入 abcd
aaaa
abc
aab
abababaababab......
UVa 1351 - String Compression
2016-02-08
题目地址
描述 有一个长度为 n ( n ≤ 2 0 0 ) n(n\le200) n ( n ≤ 2 0 0 ) 的字符串，我们现在要尽可能的压缩这个字符串，使这个字符串的长度尽可能的短。如果一个子串 S S S 连续重复 k k ......
UVa 1452 - Jump
2016-02-07
题目地址
描述 有 n ( n ≤ 5 0 0 0 0 0 ) n(n\le500000) n ( n ≤ 5 0 0 0 0 0 ) 个人顺时针排成一个圆圈，依次顺时针标号 1 − n 1 - n 1 − n 。现在从 1 1 ......
Dynamic Programming Exercises Beginner 归档题解(1)
2016-02-05
归档地址
搞这个归档模块，其实是我想写题解却懒得搞题意和输入输出之类的，这样可以方便我写分析。所以题意大家就看刘汝佳的训练指南 P93 吧。再一个是我 DP 弱的要死，赶紧总结一下方法。。。
本题解是边做题边写的，所以比较仓促，有问题欢迎留言，或是发我邮件 sengxian at live.com
题目 UVa 11584 - Partitioning by P......
UVa 1394 - And Then There Was One
2016-02-04
题目地址
描述 有 n ( n ≤ 1 0 0 0 0 ) n(n\le10000) n ( n ≤ 1 0 0 0 0 ) 个人顺时针排成一个圆圈，依次顺时针标号 1 − n 1 - n 1 − n 。一开始标号为 m m ......
UVa 1312 - Cricket Field
2016-02-03
题目地址
描述 在 W × H ( W , H ≤ 1 0 0 0 0 ) W \times H(W, H \le 10000) W × H ( W , H ≤ 1 0 0 0 0 ) 的网格中有 n ( n ≤ 1 0 0 ) n(n\le100) ......
UVa 11054 - Wine trading in Gergovia
2016-02-03
题目地址
描述 直线上有 n ( n ≤ 1 0 0 0 0 0 ) n(n\le100000) n ( n ≤ 1 0 0 0 0 0 ) 个距离为 1 1 1 个单位的村庄，从左到右依次排列。每个村庄要么要买酒，要么要卖酒，具体的数量用 ......
UVa 1382 - Distant Galaxy
2016-02-02
题目地址
描述 平面上有 n ( n ≤ 1 0 0 ) n(n\le100) n ( n ≤ 1 0 0 ) 个点，请你找出一个矩形，使得的边界上包含尽量多的点。输出边界上最多有多少个点。
样例输入 10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6
0
......
UVa 812 - Trade on Verweggistan
2016-01-22
题目地址
描述 有一种物品真实价值是 1 0 10 1 0 个单位，现在有 n ( n ≤ 5 0 ) n(n\le 50) n ( n ≤ 5 0 ) 堆该物品，每一堆有 m i ( 0 ≤ m i ≤ 2 0 ) m_i......
