ACM

HDU 5534 Partial Tree (完全背包)

HDU 5534 Partial Tree (完全背包)
题意:给出你n个节点,请添加n-1条边使得它变成一棵树。这个树必须足够“酷”,每个节点的“酷”值的定义为对于一个度数为x的节点,那么它的一个价值为f(x),求所有节点最大的酷值和。题解:dp好题。假设我们考虑到每个点还剩多少度这样分配,那么时间复杂度为O(n3),明显GG,于是我们考虑将每个点预先分配一度,由于总度数是2n-2,那么就剩下n-2度需要分配。于是我们可以将其他度数的f值变成与度数为1... 继续阅读 »
ACM

CODE FESTIVAL 2017 qual B D - 101 to 010(线性dp)

CODE FESTIVAL 2017 qual B D - 101 to 010(线性dp)
题目:给你一串由0或1组成的串,每次可以将101转换成010,求最大的可转换次数。题解:假设只有一个101那么只操作一次,但是会出现这种情况,比如1101、1011,像这些情况,第一个101转换成010之后会对接下来的字符串提供一个贡献。设一个长度为n的字符串由k个连续的1接一个0再接1个1(或者是一个1接一个0再接k个1),那么这种情况下这个串的可操作次数是k。但是对于11110111111这种... 继续阅读 »
ACM

CDOJ - 1134 男神的约会(状态压缩dp)

CDOJ - 1134 男神的约会(状态压缩dp)
状态压缩dp,利用2进制位数以及或运算保存获得的优惠券的张数。可知当前格子[i,j]只与格子[i-1, j]、格子[i, j-1]有关,所以得状态方程如下:状态方程:dp[i][j][k|1<<data[i][j]]=min(dp[i][j][k], min(dp[i][j-1][k], dp[i-1][j][k])+data[i][j]);题目地址:http://acm.uestc.... 继续阅读 »
ACM

HDU - 6024 Building Shops(背包dp)

HDU - 6024 Building Shops(背包dp)
题目的意思就是给出你n个教室的位置和在这个教室建造糖果屋的价值,这个糖果屋的右边直到下一个糖果屋之前,所有没有建造糖果屋的教室与当前糖果屋的距离也要算在花费之类。也就是说,当前糖果屋的售卖范围要延伸到下一个右边的糖果屋。所以当前糖果屋就有两种情况,建造或者不建造。比赛的时候dp方程是写出来了,但是很尴尬,一直把上一个糖果屋选择为当前最小的那个糖果屋,没考虑到可能上一个糖果屋不建造会有更优的结果。设... 继续阅读 »
ACM

HDU - 5119 Happy Matt Friends(dp,滚动数组)

HDU - 5119 Happy Matt Friends(dp,滚动数组)
题目的意思是从n个数里面选取任意个数进行异或,请问他们组合异或的值大于m的情况有多少种?定义dp[i][j]为前i个人异或得到j的情况,则dp方程为:dp[i%2][j]+=dp[(i-1)%2][j];            //当前这个人不进行异或dp[i%2][j^res[... 继续阅读 »
ACM

HDU - 5115 Dire Wolf (区间dp)

HDU - 5115 Dire Wolf (区间dp)
题目的意思是给你n头狼,然后他们自己有a点攻击,附带b点攻击。在每次攻击一头狼时,旁边两条狼会将附带伤害值加到当前狼上。意味着你会受到ai+bi-1+bi+1点攻击伤害。求杀死所有的狼你受到的伤害最小值。比赛的时候觉得dp不好做,因为以前没有接触过区间dp,所以一直拿着贪心在乱搞。区间dp,对区间长度从1到n,进行dp。随着区间长度的增加,所以遍历的次数可以为:n-len+1每次遍历的区间最大值应... 继续阅读 »
ACM

HDU - 1520 Anniversary party(树形dp)

HDU - 1520 Anniversary party(树形dp)
题目的意思是举办一个聚会,给出n个人,每个人有一定的幸福值,给出每个人的上级关系,对于直接的上下级关系,如果下级参加了上级不能参加,如果上级参加了下级不能参加。求举办这次聚会总幸福值最大数。上下级很容易想到树型,所以我们需要找到根节点,设dp[i][0]代表第i个人不去,dp[i][1]代表第i个人去,递推式如下:dp[u][0]+=max(dp[v][0], dp[v][1]);  ... 继续阅读 »
ACM

HDU - 1513 J - Palindrome(LCS,滚动数组优化)

HDU - 1513 J - Palindrome(LCS,滚动数组优化)
题目的意思是给你一个字符串,求插入最少的字符数量使得这个字符串变成回文串。把原字符串和原字符串的反转字符串求个LCS就可以求出保留的字符串,然后用总的减去即可。注意,因为数据比较多,数组会爆ME,所以要用到滚动数组优化。因为LCS只与当前行与上一行数组有关,所以我们需要保留两行的数组即可。代码:StatusAcceptedTime405msMemory1772kBLength665LangC++#... 继续阅读 »
ACM

HDU - 1502 Regular Words(大数dp)

HDU - 1502 Regular Words(大数dp)
题目的意思是给你一个数n,然后有n个A,n个B,n个C,由这些组成一个长为3n的字符串,并且对于这个字符串的每个前缀,Num(A)>=Num(B)>=Num(C)。由于数很大,所以用java写了。递推式是:dp[i][j][[k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]。dp[i][j][k]代表使用了i个A,j个B,k个C。代码:Statu... 继续阅读 »
ACM

HDU - 1501 Zipper(dp)

HDU - 1501 Zipper(dp)
题目的意思是给你三个字符串,第三个字符串要由前面两个字符串组成,并且前面两个字符串里面的字符顺序要和原来的一样。这个题dp方法有多种。代码1:StatusAcceptedTime46msMemory1892kBLength985LangC++#include <iostream> #include <cstdio> #include <... 继续阅读 »