ACM

动态规划

动态规划

[TOC]

背包问题

  1. 01背包

    for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}

  2. 完全背包

     for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
 }

  3. 多重背包1

    for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
            f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
        }
    }
}

  4. 多重背包2

    for(int i=1;i<=n;i++){
    cin>>a>>b>>c;
    int k=1;
    while(k<c){
        v[++cnt]=a*k;
        w[cnt]=b*k;
        c-=k;
        k<<=1;
    }
    if(c){
        v[++cnt]=c*a;
        w[cnt]=c*b;
    }
}
for(int i=1;i<=cnt;i++){
    for(int j=m;j>=v[i];j--){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
}

  5. 多重背包3

    #include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        memcpy(g, f, sizeof g);
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j]) -- tt;
                q[ ++ tt] = j;
                f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

  6. 分组背包

    //同组内只能选一个物品
for(int i=1;i<=n;i++){
    cin>>s[i];
    for(int j=0;j<s[i];j++){
        cin>>v[i][j]>>w[i][j];
    }
}
for(int i=1;i<=n;i++){
    for(int j=m;j>=0;j--){
        for(int k=0;k<s[i];k++){
            if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
}

  7. 有依赖的背包

    限制性条件：选第i件物品，就必须选择第j件物品，保证不会循环引用。

    一般我们称呼不依赖于别的物品的物品为主件，依赖于某主件的物品称为附件。

    一般采用树形DP 的方式来求解

    关于集合的划分，针对于附件的数量有两种方式：

    附件组合过多，则划分体积，时间复杂度为 $O(NVV)$

    附件组合不多，体积较大时，则对附件组合进行分组背包DP，时间复杂度为$O(NV2^k)$

    //以下为划分体积的方式，对附件组合进行dp，只需状态压缩遍历每种情况即可
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m, root;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N];


void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
    //先枚举所有状态体积小于等于j-v[u]的所有子节点们能够获得的最大价值
    for (int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        dfs(son); //从下往上算，先计算子节点的状态
        for (int j = m - v[u]; j >= 0; -- j) //枚举所有要被更新的状态
        {
            for (int k = 0; k <= j; ++ k)   //枚举该子节点在体积j下能使用的所有可能体积数
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    //最后选上第u件物品
    for (int j = m; j >= v[u]; -- j) f[u][j] = f[u][j - v[u]] + w[u];
    for (int j = 0; j <  v[u]; ++ j) f[u][j] = 0;   //清空没选上u的所有状态
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout << f[root][m] << endl;
    return 0;
}

最长上升子序列

int main(void) {
    int n; cin >> n;
    vector<int>arr(n);
    for (int i = 0; i < n; ++i)cin >> arr[i];

    vector<int>stk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    cout << stk.size() << endl;
    return 0;
}

最长公共子序列

 int n,m;
cin>>n>>m;
string aa,bb,a="1",b="1";
cin>>aa>>bb;
a+=aa;
b+=bb;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        f[i][j]=max(f[i][j-1],f[i-1][j]);
        if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
    }
}
cout<<f[n][m];

最长公共上升子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
int main(){
    int n;
    cin>>n;
    for (int i = 1; i <= n; i ++ ) cin>>a[i];
    for (int i = 1; i <= n; i ++ ) cin>>b[i];
    
    for (int i = 1; i <= n; i ++ )
    {   
        int maxv = 1;
        for(int j = 1; j <=n ; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
            if (b[j] < a[i]) maxv = max(f[i][j]+1, maxv);
        }
    }
    int res = 0;
    for (int i = 1;i <= n; i ++) res = max(res, f[n][i]);
    cout<<res;
    return 0;
}

单调队列优化

 for (int i = 1; i <= n; i ++ )
{
    while (hh <= tt && i - que[hh] > m) hh ++ ;
    res = max(res, s[i] - s[que[hh]]);
    while (hh <= tt && s[que[tt]] >= s[i]) tt -- ;
    que[ ++ tt] = i;
}

树形DP之换根DP

//换根DP 一般分为三个步骤：
//1.指定任意一个根节点
//2.一次dfs遍历，统计出当前子树内的节点对当前节点的贡献
//3.一次dfs遍历，统计出当前节点的父节点对当前节点的贡献，然后合并统计答案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = N << 1, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], up[N];
int s1[N], s2[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1(int u, int father)
{
    // d1[u] = d2[u] = -INF;  //这题所有边权都是正的，可以不用初始化为负无穷
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u);
        if (d1[j] + w[i] >= d1[u])
        {
            d2[u] = d1[u], s2[u] = s1[u];
            d1[u] = d1[j] + w[i], s1[u] = j;
        }
        else if (d1[j] + w[i] > d2[u])
        {
            d2[u] = d1[j] + w[i], s2[u] = j;
        }
    }
    // if (d1[u] == -INF) d1[u] = d2[u] = 0; //特判叶子结点
}
void dfs2(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        if (s1[u] == j) up[j] = w[i] + max(up[u], d2[u]);   //son_u  = j，则用次大更新
        else up[j] = w[i] + max(up[u], d1[u]);              //son_u != j，则用最大更新
        dfs2(j, u);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dfs1(1, -1);
    dfs2(1, -1);

    int res = INF;
    for (int i = 1; i <= n; i ++ ) res = min(res, max(d1[i], up[i]));
    printf("%d\n", res);

    return 0;
}