ACM——动态规划模板

参考网上众多大神整理得出以下模板，如有不对之处，欢迎讨论

1. 背包问题：
   （1）01背包：

void bag01(int cost,int weight)  {  
    for(i = v; i >= cost; --i)  
    dp[i] = max(dp[i], dp[i-cost]+weight);  
}  

1
2
3
4
5

（2）完全背包：

void complete(int cost, int weight)  {  
    for(i = cost ; i <= v; ++i)  
    dp[i] = max(dp[i], dp[i - cost] + weight);  
}  
1
2
3
4

（3） 多重背包：

void multiply(int cost, int weight, int amount)  {  
    if(cost * amount >= v)  
        complete(cost, weight);  
    else{  
        k = 1;  
        while (k < amount){  
            bag01(k * cost, k * weight);  
            amount -= k;  
            k += k;  
        }  
        bag01(cost * amount, weight * amount);  
    }  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 最长公共子序列LCS　　Longest Common Subsequence
   找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。cnblogs与belong，最长公共子序列为blog（cnblogs, belong），最长公共子串为lo（cnblogs, belong）这两个问题都是用空间换空间，创建一个二维数组来记录之前的每个状态

void solve() {  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < m; ++j) {  
            if (s1[i] == s2[j]) {  
                dp[i + 1][j + 1] = dp[i][j] + 1;  
            }else {  
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);  
            } } }
}  

1
2
3
4
5
6
7
8
9
10

3. 最长递增序列
   问题：
   设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
   第一种：
   排序，然后用LCS来解决：设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。
   第二种：
   时间复杂度O(N^2)的算法：
   LIS[i]：表示数组前i个元素中（包括第i个），最长递增子序列的长度
   LIS[i] = max{ LIS[i] , LIS[k]+1 }, 0 <= k < i, a[i]>a[k]
   LIS数组的值表示前i个元素的最长子序列。i从第一个元素到最后一个元素遍历一遍，j从第一个元素到第i个元素遍历，如果第i个元素大于j，并且LIS[J] + 1比LIS[I]还大就更新，相当于把j加入到这个递增序列了。
   （1）求最长递增子序列的长度O(N^2)

int Arr[30010],List[30010];
int LIS(int *Arr,int N)    //arr[]存放的是待求数组
{
    int Max = 0;        //max为最大递增子序列的长度
    for(int i = 1; i <= N; ++i)
        List[i] = 1;    //lis[i] 存放i之前的最大递增子序列的长度，初始都为1
    for(int i = 2; i <= N; ++i)
        for(int j = 1; j < i; ++j)    //遍历i之前所有位置
            if(Arr[i] >= Arr[j] && List[i]<List[j]+1)
                List[i] = List[j] + 1;
            //arr[i]>arr[j]为递增
            //lis[i]<lis[j] + 1确保为当前最长递增序列
    for(int i = 1; i <= N; ++i)
        if(Max < List[i])
            Max = List[i];
    return Max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）求最长递增子序列的长度O(NlogN)

int Stack[10010];
int LIS(int *Arr,int N)
{
    int top = 0;
    Stack[top] = -1;
    for(int i = 1; i <= N; ++i)
    {
        if(Arr[i] > Stack[top])
            Stack[++top] = Arr[i];
        else
        {
            int low = 1;
            int high = top;
            while(low <= high)
            {
                int mid = (low + high)/2;
                if(Arr[i] > Stack[mid])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            Stack[low] = Arr[i];
        }
    }
    return top;
}
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

4. 最大连续子序列和
   给定一个整数序列，找出所有连续子序列中元素和最大的一个，并找到起点和终

int a[110000],N,pos1,pos2,Start,End;
//Start、End存储最大连续子序列的起点和终点
int MaxSubSum(int *a)
{
    int MaxSum = a[0],Sum = a[0];
    pos1 = pos2 = Start = End = 0;
    for(int i = 1; i < N; ++i)
    {
        Sum += a[i];
        if(Sum < a[i])
        {
            Sum = a[i];
            pos1 = i;
            pos2 = i;
        }
        else
        {
            pos2 = i;
        }
        if(MaxSum < Sum)
        {
            MaxSum = Sum;
            Start = pos1;
            End = pos2;
        }
    }
    return MaxSum;
}
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

5. 最长回文子序列
   给一个字符串，找出它的最长的回文子序列LPS的长度。例如，如果给定的序列是“BBABCBCAB”，则输出应该是7，“BABCBAB”是在它的最长回文子序列。

char s[2020];
int dp[2020][2020];
//dp[i][j]表示s[i~j]最长回文子序列
int LPS(char *s)
{
    memset(dp,0,sizeof(dp));
    int len = strlen(s);
    for(int i = len-1; i >= 0; --i)
    {
        dp[i][i] = 1;
        for(int j = i+1; j < len; ++j)
        {
            if(s[i] == s[j])    //头尾相同，最长回文子序列为去头尾的部分LPS加上头和尾
                dp[i][j] = dp[i+1][j-1] + 2;
            else    //头尾不同，最长回文子序列是去头部分的LPS和去尾部分LPS较长的
                dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
        }
    }
    return dp[0][len-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6. 最长回文子串
   给一个字符串，找出它的最长的回文子串(连续的串)的长度。

char str[2000020],s[2000020];
//str为待求的原串,s为处理后的新串
int P[2000020];
//P［i］记录的是以字符str［i］为中心的最长回文串的半径
void Pre(char *str)
{
    int len = strlen(str);
    s[0] = '$';
    s[1] = '#';
    for(int i = 0; i < len; ++i)
    {
        s[i*2+2] = str[i];
        s[i*2+3] = '#';
    }
    s[len*2+2] = '\0';
}
//返回最长回文子串长度
int Manacher(char *s)
{
    int Max = 0;
    int len = strlen(s);
    int id = 0;
    for(int i = 1; i < len; ++i)
    {
        if(Max > i)
            P[i] = min(P[2*id-i],P[id]+id-i);
        else
            P[i] = 1;
        while(s[i+P[i]] == s[i-P[i]])
            P[i]++;
        if(P[i]+i > Max)
        {
            Max = P[i]+i;
            id = i;
        }
    }
    int ans = 0;
    for(int i = 2; i < len; ++i)
        if(ans < P[i])
            ans = P[i];
    return ans-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
37
38
39
40
41
42

7. 最小编辑距离
   给定一个长度为m和n的两个字符串，设有以下几种操作：替换（R），插入（I）和删除（D）且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小（操作）数量。

int dp[1010][1010],len1,len2;
char s1[1010],s2[1010];
int EditDist(char *s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
//当两个字符串的大小为0，其操作距离为0。
//当其中一个字符串的长度是零，需要的操作距离就是另一个字符串的长度. 
    for(int i = 0; i <= len1; ++i)
        dp[i][0] = i;
    for(int i = 0; i <= len2; ++i)
        dp[0][i] = i;
    for(int i = 1; i <= len1; ++i)
    {
        for(int j = 1; j <= len2; ++j)
        {
            if(s1[i-1] == s2[j-1])  //对齐s1[i-1]和s2[j-1]，不需改变
                dp[i][j] = dp[i-1][j-1];
            else    
                dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;
            //s1前缀右对齐,s2前缀右为' ',删除s1第i个字符 -> dp[i-1][j]
            //s2前缀右对齐,s1前缀右为' ',删除s2第j个字符 -> dp[i][j-1]
            //s1前缀右对齐,s2前缀右对齐,i、j不一样，替换 -> dp[i-1][j-1]
        }
    }
    return dp[len1][len2];
}
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

8. 树形DP—依赖背包模板

void DP(int x){
    for(int i=0;i<=t;i++){
        dp[x][i]=p[x].val;
    }
    for(int i=0;i<son[x].size();i++){
        if(in[son[x][i]]==1)
            continue;
        DP(son[x][i]);
        int lim=val[x][i];
        for(int j=t;j>=lim;j--){
            for(int k=0;k<=j-lim;k++)
                dp[x][j]=max(dp[x][j-lim-k]+dp[son[x][i]][k],dp[x][j]);
        }
    }
    return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例题:
题目：hdoj1561The more, The Better（树形dp，依赖背包）
题意：ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？
这题的关系就是裸地依赖背包，用树形dp解。
题解：首先，限制条件是选择m个物品，而每个物品最多选一次，跟0-1背包的区别在于有依赖关系，那么这层依赖关系我们可以借助于一个树来解决。借助dfs，从根节点开始dfs，然后直到叶子节点，回朔的时候进行0-1背包dp。

#include <vector>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 150;
using namespace std;
int n,m;
int dp[N][N],vis[N];  //dp[i][j]表示在节点i，从以i为根节点的子树下选择j个城市的最大价值
int cap[N],val[N];
vector<int> v[N];
void creat(int o)
{
    for(int i=0; i<v[o].size(); i++)
    {
        int t=v[o][i];
        if(vis[t] == 0 && v[t].size()>0)
            creat(t);
        for(int j = m ; j > 1 ; j--)   //j>1表示此节点一定要取 0-1背包
        {
            for(int k=1; k<j; k++) //枚举给当前节点的其他子树留多少可选择的城市
                dp[o][j]=max(dp[o][j],dp[o][k]+dp[t][j-k]);
        }
    }
}
int main(){
    while(cin >> n >> m , n&&m){
        m ++; // 加一个根节点
        Del(dp,0);
        for(int i = 1 ; i <= n ; i ++){
            int a , b;
            cin >> a >> b;
            v[a].push_back(i);
            for(int j = 1 ; j <= m ; j++)
                dp[i][j] = b;  // 初始化时，每个节点，所有状态都是拿自己一个
        }
        creat(0);
        for(int i = 0 ; i <= n ; i ++)
            v[i].clear();
        cout << dp[0][m] << endl;
    }
    return 0;
}
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
37
38
39
40
41
42
43
44
45