CSP2019-J，第二轮T3《纪念品》

https://www.luogu.com.cn/problem/P5662

暴力，完全背包

//卑微的10pts，考场上心理建设问题
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int g[N][N];
int T, n, m;

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

    if (T == 1)
    {
        printf("%d\n", m);
    }

    return 0;
}

//45pts，暴力分
#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1e7 + 10;

int a[N][N];
int T, n, m;
int f[N];
int zhuan;

void dfs(int qian, int js, int j, int t)  //j天买入，t天卖出
{
    if (js > zhuan) zhuan = js;

    for (int i = 1; i <= n; i++)
    {
        if (qian - a[j][i] >= 0)
            dfs(qian - a[j][i], js + a[t][i] - a[j][i], j, t);
    }
}

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

    f[0] = m;
    for (int i = 1; i <= T; i++) //枚举买入和卖出的时间点
    {
        zhuan = 0;
        for (int j = 1; j < i; j++)
            dfs(f[j], f[j], j, i);

        f[i] = max(zhuan, f[i - 1]);
    }

    printf("%d\n", f[T]);

    return 0;
}

//完全背包，空间优化，100pts
//每一天手里的钱，看做背包的体积，前一天物品的价值是物品的体积，今天减去昨天的价格是收益，也就是物品的价值
//需要使用完全背包的一维优化版本，小心MLE
#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1e7 + 10;

int dp[M];
int a[N][N];
int T, n, m;

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

    for (int now = 2; now <= T; now++)
    {
        memset(dp, 0, sizeof dp);

        for (int i = 1; i <= n; i++)
            for (int j = a[now - 1][i]; j <= m; j++)
                dp[j] = max(dp[j], dp[j - a[now - 1][i]] + (a[now][i] - a[now - 1][i]));

        m += dp[m];
    }

    printf("%d\n", m);

    return 0;
}