kuangbin专题十二 基础DP

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