kuangbin专题十二 基础DP

Posted on | In |

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]| 离散化