Posts match “ DP ” tag:

http://community.topcoder.com/stat?c=round_overview&rd=15846

A题水过。。
推广
若文本和子序列的长度均达到,下面代码的做法必然会TLE,所以需要一个的做法:
很简单,只需用一个26字节大小的bool数组统计中没出现的字母,然后同时遍历即可。

B题暴力,复杂度(也可以只判断与分界点的狗的相对位置,复杂度
待解决
是否存在一个的算法呢?

C题状压,复杂度,关键在于把数字分成1~10和大于10两组,作为两个维度。

继续阅读

http://poj.org/problem?id=3688

从i=0开始,画一颗必胜/必败态的转移树,不难分析出:
如果W只能表示成奇数个数字之和,则先手必胜。
如果W只能表示为偶数个数字之和,则后手必胜。
如果W可以表示为奇数个或偶数个数字之和,则谁胜利都有可能。

转移方程:
dp[j][1] = dp[j - a[i]][0]
dp[j][0] = dp[j - a[i]][1]

最后判断:if (dp[i][1] && !dp[i][0]) ++ans;

继续阅读

http://poj.org/problem?id=3666

首先基于贪心的想法,变动后的数组中的元素只可能是原数组中的元素。

我们用a数组存原始数组,b数组存对a从小到大排序后的结果。
用dp[i][j]表示前i个元素的最后元素为原序列的第j小元素时的最优解,
则dp[i][j] = MIN{dp[i-1][k]} + abs(a[i]-b[j]) (0<=k<=j)
边循环边求MIN{dp[i-1][k]},同时用滚动数组优化,就可以在的时间复杂度和O(n)的空间复杂度下解决此题。

继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2395

首先可以得出一个结论,那就是换灯泡的时候,要么都不换,要么都换。(因为部分换的话电源就要买两种)
那么就可以把每种灯泡看成一个整体。

状态:dp[i]表示灯泡1~i的最小费用。
转移:前j个先用最优方案买,然后j+1~i都用第i种的电源,即dp[i]=min{dp[j]+(sum[i]-sum[j])*c[i]+k[i]}

继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4500

状态:dp[i][j] 表示两个队列分别取前i个和前j个时,对最终结果的「贡献值」(指已在队列但尚未结束的颜色到i,j的距离之和)。
要计算这一「贡献值」,必须要记录每一颜色在两队列中的开始和结束位置。
转移:dp[i][j] = min(dp[i-1][j] + c[i-1][j], dp[i][j-1] + c[i][j-1]),其中c[i][j]表示此时已在队列但尚未结束的颜色个数

继续阅读

The Minima Game

题目:给你 n 个数(1 <= n <= 1000000),每个数 <= 1000000000。现在两个人轮流取这些数,每次可以取若干个数,得分是这些数的最小值,直到取完为止,问在最优决策下,先手对后手的最大分差是多少。

先排序。
设dp[i]为只取前i个数的最大分差,此时新加进来一个更大的数,我们有两种策略:

  1. 取这个数但不取到这个数(最终得分小于这个数)
  2. 取并且取到这个数(最终得分就是这个数)

情况1就是dp[i],情况2就是a[i]-dp[i],因为此时该对面先取。
所以dp[i+1]=max(dp[i],a[i]-dp[i])

代码就不贴了。