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 <... 继续阅读 »
ACM

HDU - 1466 计算直线的交点数(dp)

HDU - 1466 计算直线的交点数(dp)
题目都是中文的,好懂。一开始当作树形dp去做,wa了,发现有些情况还没考虑到。一下是摘自Even的题解n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,所以n=20的话,最大的交点数是190本题是求有多少种交点数:容易列举出N=1,2,3的情况:00,10,2,3如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):1、第四条与其余直线全部... 继续阅读 »
ACM

ACdream - 1063 平衡树(字典树)

ACdream - 1063 平衡树(字典树)
比赛时一看就是字典树,但是当时脑子短路,想了一些莫名其妙的东西就没做了。事后补上~~~(求最大最小也就是把0变1,1变0,变成两个不同的编码而已。因为字典树用的指针版本,如果不在使用后delete就会报ME)代码:StatusAcceptedTime1064msMemory2856kBLength1796LangC++#include <iostream> #include... 继续阅读 »
ACM

HihoCoder - 1339 D - Dice Possibility(递推)

HihoCoder - 1339 D - Dice Possibility(递推)
题目意思很好懂,给你n个骰子、请问滚出数字为m的概率是多少?这个很坑爹啊,开始想用母函数来搞,后来发现不对劲啊,n有100,开100次方早就是大数了,那怎么办,只能按照常规方法递推,然后还因为没考虑边界问题WA一次。心痛。代码:StatusAcceptedTime1msLength853LangG++#include <iostream> #include <... 继续阅读 »
ACM

HDU - 1712 ACboy needs your help(DP)

HDU - 1712 ACboy needs your help(DP)
题目意思是给你n节课,m天,接下来给出n行,每行有m个数,代表着第i节课学习j天能获得的价值。求能获得的最大价值。递推式:dp[j] = max(dp[j], dp[j-k]+res[i][k])意思就是学习j天的最大价值是当前价值,还是当前价值减去k天,用这k天来学习新的课程的价值。代码:StatusAcceptedTime93msMemory1772kBLength705LangC++#inc... 继续阅读 »
ACM

HYSBZ 1452 颜色计数(二维树状数组)

HYSBZ 1452 颜色计数(二维树状数组)
对每个颜色分别建立树状数组即可。其他的都是模板思想了。然后,树状数组嘛,很神奇,自己搜索一下资料看看,仔细想想就理解了代码:StatusAcceptedTime4768msMemory42960kBLength1365LangC++#include <iostream> #include <cstdio> #include <algo... 继续阅读 »
ACM

HDU 1085 Holding Bin-Laden Captive!(数学,母函数)

HDU 1085	Holding Bin-Laden Captive!(数学,母函数)
给出你定值硬币的数量,问你这些硬币不能组成的最小价值是多少。这个题嘛,乱搞,dp,找规律都行,但是学长说这个用母函数做。。。乱搞代码:StatusAcceptedMemory1560kBLength486LangG++#include <iostream> #include <cstdio> using namespace std... 继续阅读 »