头像

Enchanted_77


访客:5938

离线:2个月前


活动打卡代码 AcWing 1057. 股票买卖 IV

Enchanted_77
2个月前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, K = 110, inf = 0x3f3f3f3f;
int f[N][K][2];
int n, k;
int w[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) scanf("%d", w + i);

    // initialize
    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i ++) f[i][0][0] = 0;

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

    int res = 0;
    for (int i = 0; i <= k; i ++) res = max(res, f[n][i][0]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

Enchanted_77
2个月前

状态机模型:

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;

int t, n;
int w[N];
int f[N][2];

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        for (int i = 0; i < n; i ++) scanf("%d", w + i);

        f[0][1] = w[0];

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

        cout << max(f[n - 1][0], f[n - 1][1]) << endl;
    }


    return 0;
}

普通模型:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int t, n;
int w[N], f[N];

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        for (int i = 1; i <= n; i ++) scanf("%d", w + i);

        f[1] = w[1];

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

        cout << f[n] << endl;
    }
}



Enchanted_77
4个月前
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int f[N], g[N];
int n, m;

int main()
{
    cin >> n >> m;

    g[0]= 1;
    for (int i = 1; i <= n; i ++)
    {
        int v, w;
        scanf("%d%d", &v, &w);

        for (int j = m; j >= v; j --)
        {
            int tm = f[j - v] + w;
            if(f[j] < tm) f[j] = tm, g[j] = g[j - v];
            else if(f[j] == tm) g[j] = (g[j] + g[j - v]) % mod;
        }
    }

    int id = 0;
    for (int i = 0; i <= m; i ++) if(f[i] > f[id]) id = i; // 找出一个最优方案所占用的体积

    int res = 0;
    for (int i = 0; i <= m; i ++)
        if(f[i] == f[id]) res = (res + g[i]) % mod; // 如果这是一个最优方案,就加入答案中

    cout << res << endl;

    return 0;
}



Enchanted_77
4个月前

树形DP框架,在框架内部,只需要考虑两层的关系:根+子树,用递归的思路来考虑
区别于线性DP, 将前i项(线性)换成以所有以i为根的子树中的所有物品
每一棵子树:选不选,怎么选 –> 在这样的枚举情况下来取最大值
kkk.png

每一棵子树内部的划分方法:以体积来划分(因为如果用子树中的节点来划分的话,存不下)

如果子树中有k个点,最坏情况下,划分为2^k级别的方案数,若按照体积来划分,那么情况有m种,0~m-1
jjj.png
相当于分组背包问题,将每个子树看成一个物品组,从m种方案中选一个出来
因此,按照分组背包的方式循环一遍就可以了

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 110;

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

void add(int a, int b)
{
    e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs(int 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 ++) // 循环方案, 方案按照体积分类
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }

    for (int i = m; i >= 0; i --) // 把根节点加入,注意要倒序更新
    {
        if(i >= v[u]) f[u][i] = f[u][i - v[u]] + w[u];
        else f[u][i] = 0;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        int p;
        scanf("%d%d%d", v + i, w + i, &p);
        if(p == -1){
            root = i;
            continue;
        }
        add(p, i);
    }

    dfs(root);

    cout << f[root][m] << endl;
}



Enchanted_77
4个月前
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 110;

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

void add(int a, int b)
{
    e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs(int 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 ++) // 循环方案, 方案按照体积分类
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }

    for (int i = m; i >= 0; i --) // 把根节点加入,注意要倒序更新
    {
        if(i >= v[u]) f[u][i] = f[u][i - v[u]] + w[u];
        else f[u][i] = 0;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        int p;
        scanf("%d%d%d", v + i, w + i, &p);
        if(p == -1){
            root = i;
            continue;
        }
        add(p, i);
    }

    dfs(root);

    cout << f[root][m] << endl;
}


活动打卡代码 AcWing 426. 开心的金明

Enchanted_77
4个月前
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 30010, V = 10010;
int v[V], p[V];
int f[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i ++) scanf("%d%d", v + i, p + i);

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

    cout << f[n] << endl;

    return 0;
}


活动打卡代码 AcWing 1013. 机器分配

Enchanted_77
4个月前
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 15, M = 20;
int w[N][M];
int f[N][M];
int res[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) scanf("%d", &w[i][j]);


    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
            for (int k = 0; k <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
    int j = m;            
    for (int i = n; i >= 1; i --) // 从后往前推,从第n个公司开始倒推
        for (int k = 0; k <= j; k ++) // 遍历第n个公司的所有可能
            if(f[i][j] == f[i - 1][j - k] + w[i][k]) // 如果找到了转移到这个状态的前一个状态
            {
                res[i] = k;
                j -= k; // 体积也相应减小
                break;
            }


    cout << f[n][m] << endl;

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

    return 0;
}



Enchanted_77
4个月前

批注 2020-05-05 113402.png

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int K = 1010, N = 25, M = 85;
int f[N][M];

int main()
{
 memset(f, 0x3f, sizeof f);
 f[0][0] = 0;
 int k;
 int vo, vn;
 cin >> vo >> vn;
 cin >> k;
 for (int i = 0; i < k; i ++){
     int o, n, w;
     scanf("%d%d%d", &o, &n, &w);
     for (int jo = vo; jo >= 0; jo --)
        for (int jn = vn; jn >= 0; jn --)
            f[jo][jn] = min(f[jo][jn], f[max(0, jo - o)][max(0, jn - n)] + w);
 }

 cout << f[vo][vn] << endl;

 return 0;
 }


活动打卡代码 AcWing 1020. 潜水员

Enchanted_77
4个月前

```

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int K = 1010, N = 25, M = 85;
int f[N][M];

int main()
{
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
int k;
int vo, vn;
cin >> vo >> vn;
cin >> k;
for (int i = 0; i < k; i ++){
int o, n, w;
scanf(“%d%d%d”, &o, &n, &w);
for (int jo = vo; jo >= 0; jo –)
for (int jn = vn; jn >= 0; jn –)
f[jo][jn] = min(f[jo][jn], f[max(0, jo - o)][max(0, jn - n)] + w);
}

 cout << f[vo][vn] << endl;

 return 0;

}
```




Enchanted_77
4个月前

批注 2020-05-05 105945.png

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1010, M = 110;
int f[M][M];
int v[N], w[N], value[N];
int volume, weight;
int n;

int main()
{
    cin >> n >> volume >> weight;

    for (int i = 0; i < n; i ++) scanf("%d%d%d", v + i, w + i, value + i);

    for (int i = 0; i < n; i ++)
        for (int j = volume; j >= v[i]; j --)
            for (int k = weight; k >= w[i]; k --)
                f[j][k] = max(f[j][k], f[j - v[i]][k - w[i]] + value[i]);

    cout << f[volume][weight] << endl;

    return 0;
}