kuangbin 专题十二 基础DP
LIS
dp[ i ]代表前i个数的最长子序列大小
dp[ i ] =max { dp[ j ] + 1 } ( val[ j ] < val[ i ] )
$ O ( n^2 ) $
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int dp[ N ], val[ N ]; int LIS ( int n ) { int mx = 0; for ( int i = 0; i < n; ++i ) { dp[ i ] = 1; for ( int j = 0; j < i; ++j ) { if ( val[ j ] < val[ i ] && dp[ i ] < dp[ j ] + 1 ) dp[ i ] = dp[ j ] + 1; } if ( mx < dp[ i ] ) mx = dp[ i ]; } return mx; } |
$ O ( nlgn ) $
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
http://blog.csdn.net/shuangde800/article/details/7474903
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | int val[ N ];//输入的值 int len;//ed数组的长度(LIS长度) int ed[ N ];//每个长度的序列的末尾 //下界,返回 >= 所查找对象的第一个位置 int binary_search ( int i ) { int left, right, mid; left = 0, right = len; while ( left < right ) { mid = left + ( right - left ) / 2; if ( ed[ mid ] >= val[ i ] ) right = mid; else left = mid + 1; } return left; } void LIS ( int n ) { ed[ 1 ] = val[ 1 ]; len = 1; for ( int i = 2; i <= n; ++i ) { //更新最长的末尾 if ( val[ i ] > ed[ len ] ) ed[ ++len ] = val[ i ]; //产生了新的序列,改变旧的长度的末尾 else { // 如果用STL: pos=lower_bound(ed,ed+len,val[i])-ed; int pos = binary_search ( i ); ed[ pos ] = val[ i ]; } printf ( "%d\n", len ); } } |
LCS
dp[ i ][ j ] 代表两个字符串前i / j 个下的最长大小
dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + 1 ( val[ i ] == val[ j ] )
dp[ i ][ j ] = max ( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ) ( != )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | //CLRS 15.4 int len1, len2; char s1[ N ], s2[ N ]; int dp[ N ][ N ]; inline int max ( int a, int b ) { return a > b ? a : b; } void LCS () { for ( int i = 1; i <= len1; i++ ) { for ( int j = 1; j <= len2; j++ ) { if ( s1[ i ] == s2[ j ] ) dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + 1; else dp[ i ][ j ] = max ( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ); } } } void Print ( int i, int j ) { //当最长的子序列搜索完,但其中一串仍有剩余时,输出 if ( i == 0 || j == 0 ) { return; } //找到公共字符 if ( s1[ i ] == s2[ j ] ) { Print ( i - 1, j - 1 ); printf ( "%c", s1[ i ] ); } else if ( dp[ i - 1 ][ j ] > dp[ i ][ j - 1 ] ) { Print ( i - 1, j ); } else { Print ( i, j - 1 ); } } |
完全背包
dp[ i ]代表背包重i的时候最大的价值
dp[ i ] = min ( dp[ i ], dp[ i - w[ j ] ] + v[ j ] )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int v[ N ], w[ N ]; // value,weight int dp[ N ]; //n个物品,最多装wei的东西 int knapsack ( int n, int wei ) { memset ( dp, INF, sizeof ( dp ) ); dp[ 0 ] = 0; for ( int i = 1; i <= wei; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i >= w[ j ] ) dp[ i ] = min ( dp[ i ], dp[ i - w[ j ] ] + v[ j ] ); } } return dp[ wei ]; } |
题目列表
A - Max Sum Plus Plus HDU - 1024
n个数,要求分成m组,使m组的和加起来得到最大值。
dp[i][j]表示前j个数分成i组的最大值。
dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j])
B - Ignatius and the Princess IV HDU - 1029
给n(奇数)个数,定义特殊的数为在序列中出现次数不少于(n+1)/2次的数,找出这个特殊的数
一边输入一边记录个数就好了
C - Monkey and Banana HDU - 1069
给定箱子种类数量n,及对应长宽高,每个箱子数量无限,求其能叠起来的最大高度是多少(上面箱子的长宽严格小于下面箱子)
按照长排序,在求宽关于高的LIS
D - Doing Homework HDU - 1074
有n门功课需要完成,每一门功课都有时间期限以及你完成所需要的时间,如果完成的时间超出时间期限多少单位,就会被减多少学分,问以怎样的功课完成顺序,会使减掉的学分最少,有多个解时,输出功课名排列最小的一个。
15个作业状态压缩来做
枚举每一个状态,枚举每个状态新增的那个节点,再计算最小并记录前一个状态
E - Super Jumping! Jumping! Jumping! HDU - 1087
从起点到达终点,只能前行不能后退,且下一步必须比前面的点的值大,求所有走的点的值总和最大是多少。
dp[i] = max(dp[k] + a[j]); 1<=k<=i-1;
最大递增子串和。
F - Piggy-Bank HDU - 1114
给出存钱罐本身的重量和装钱后的重量,以及存钱罐中钱的面值和重量,求存钱罐装满时,钱的总和最小是多少
完全背包解题,每种钱币都可以装无限个,注意初始化的值
dp[ i ] = min ( dp[ i ], dp[ i - w[ j ] ] + v[ j ] );
G - 免费馅饼 HDU - 1176
0—10的点,不同时间在每个点上掉下来物品,只能到达左右两边距离为1和本身所在的位置,求最大物品数
dp[x][t] = max ( dp[x-1][t-1],dp[x][t-1],dp[x+1][t-1]) + v[x][t]
H - Tickets HDU - 1260
单张或两张一起买,给出一个一个买票和两个两个买票的时间,求最少
dp[ i ] = min ( dp[ i - 1 ] + s[ i ], dp[ i - 2 ] + d[ i - 1 ] );
I - 最少拦截系统 HDU - 1257
求有多少个递减序列
反过来,转换成求整个系列有多少个LIS,则是所求的组数
J - FatMouse’s Speed HDU - 1160
给n个老鼠的体重和速度,求找出一个最长的序列,此序列体重递增速度递减
按体重递增排序,再求最长递增(此递增表示体重递增速度递减)子序列。
dp[i] = max(dp[j]+1) 0<=j<=i-1
K - Jury Compromise POJ - 1015
必须满足辩方总分D和控方总分P的差的绝对值|D-P|最小。如果有多种选择方案的 |D-P| 值相同,那么选辩控双方总分之和D+P最大的方案即可。
dp(j, k)表示,取j 个候选人,使其辩控差为k 的所有方案中,辩控和最大的那个方案的辩控和。
综上:dp[j][k]=dp[j-1][k-V[i]]+S[i]
正向计算,输出的时候就用正向的输出了,不过每次都要查找下一个位置是否在之前用过了
L - Common Subsequence POJ - 1458
LCS
LCS模板
M - Help Jimmy POJ - 1661
老鼠在时刻0从高于所有平台的某处开始下落.当Jimmy落到某个平台上时,游戏者选择让它向左还是向右跑.当Jimmy跑到平台的边缘时,开始继续下落。Jimmy每次下落的高度不能超过MAX
dp[i][0] = min(dp[k][0]+l[i]-l[k], dp[k][1]+r[i]-l[k]) + h[i]-h[k]; (左左和左右取最小)
dp[i][1] = min(dp[k][0]+r[i]-l[k], dp[k][1]+r[i]-r[k]) + h[i]-h[k];(右左和右右取最小)
N - Longest Ordered Subsequence POJ - 2533
LIS
LIS模板
O - Treats for the Cows POJ - 3186
n个数在一个双端队列中,每次从队首或队尾出。出的第n个数乘以n,最后加起来,求最大和。
dp[i][j] 代表从i取到j的最大总数
dp[i][j] = max(dp[i+1][j]+a[i] * (n+i-j) , dp[i][j-1]+a[j] * (n+i-j));
P - FatMouse and Cheese HDU - 1078
给定一幅图,每个点有一定权值,现在有一只老鼠在起始点(0,0),他能水平或者垂直移动1~k格之后,停在某点并获得权值,而且每次移动后所在的点,都要比刚离开的那个点的权值更大,求最多能获得多少权值。
DP / Memoized
dp[ x ][ y ] = dp[ xx ][ yy ] + val[ x ][ y ]
Q - Phalanx HDU - 2859
给了一个字符串矩阵,求以次对角线方向对称的最大对称矩阵。
每次只需求最外面一层对称个数sum,再和右上角对称矩阵大小加一取最小就行,就求出当前小矩阵的最大对称矩阵。最后取个所有对称矩阵大小的最大值就行。
dp[i][j] = min(sum,dp[i-1][j+1]+1);
R - Milking Time POJ - 3616
奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶,时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能继续下一次产奶,求Bessie最大的挤奶量。
dp[ i ] = max ( dp[ j ] + node[ i ].val, dp[ i ] ) ( node[ j ].ed <= node[ i ].st )
S - Making the Grade POJ - 3666
农夫约翰想修一条尽量平缓的路,路的每一段海拔是A_i,修理后是B_i,花费|A_i – B_i|,求最小花费。
dp[i][j] = min(dp[i – 1][k]) + |A[i] – B[j]| 离散化