【动态规划专题训练】JSU_ACM_第二小组
http://acm.hdu.edu.cn/diy/contest_show.php?cid=6939
1001 Max Sum
经典的最大子段和需要记录首尾
1002 Constructing Roads In JGShining's Kingdom
排列的LCS可以转换为LIS
1003 Humble Numbers
DP或者搜索
1004 Dividing
01背包
1005 Monkey and Banana
LIS变种
1006 Doing Homework
状态DP没做
1007 FatMouse and Cheese
记忆化搜索
1008 Super Jumping! Jumping! Jumping!
LIS
1009 Piggy-Bank
完全背包
1010 Employment Planning
d[i][j]=min{d[i-1][k]+w(j,k)}
1011 Common Subsequence
LCS
1012 FatMouse's Speed
LIS
1013 Eddy's research II
递推
1014 免费馅饼
d[i][j]=max{d[i-1][k]}
1015 I NEED A OFFER!
01背包d[j]=max(d[j],d[j-v[i]]+w[i]-w[i]*d[j-v[i]])
1016 Pascal's Travels
记忆化搜索或DP
d[i][j+a[i][j]]+=d[i][j];d[i+a[i][j]][j]+=a[i][j];
1017 最少拦截系统
贪心？选能拦截的最低的那套系统
两种做法,一是贪心,从后往前贪;二是DP;
if(v[i]>max{dp[j]}) (0<=j<len) dp[len++]=v[i];
1018 Function Run Fun
记忆化搜索
1019 The Peanuts
没做，貌似贪心
1020 银河跳舞机大赛
没看
1021 漫步校园
BFS+DFS记忆化搜索
1022 Function Run Fun
1023 Distribute Message
d[i]+=d[i-j]
1024 Bone Collector
01背包
1025 搬寝室
dp[i][j]=min(dp[i-2][j-1]+s[i],dp[i-1][j])