[多维DP] 洛谷P1855 榨取kkksc03（简单加维）

题目

思路

简单加维即可，本题用记忆化搜索会直截了当一点。

ans=max{dp(i−1,m,t),dp(i−1,m−mt[i],t−tt[i])+1}$$ans=max\left\{dp(i-1,m,t),dp(i-1,m-mt[i],t-tt[i])+1\right\}$$

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;

const int maxn = 100 + 10;
const int maxs = 200 + 10;
int n, m, t, mt[maxn], tt[maxn], d[maxn][maxs][maxs];

int dp(int i, int ml, int tl) {
    if (i < 1) return 0;
    int &ans = d[i][ml][tl];
    if (ans != -1) return ans;
    ans = 0;
    if (ml >= mt[i] && tl >= tt[i])
        ans = max(ans, dp(i - 1, ml - mt[i], tl - tt[i]) + 1);
    ans = max(ans, dp(i - 1, ml, tl));
    return ans;
}

int main() {
    scanf("%d%d%d", &n, &m, &t);
    _rep(i, 1, n)
        scanf("%d%d", &mt[i], &tt[i]);

    memset(d, -1, sizeof(d));
    printf("%d\n", dp(n, m, t));

    return 0;
}