Luogu P4138 [JOISC2014]挂饰

题目描述

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

Solution

我们令 $f[i][j]$ 表示前 $i$ 个挂饰，有 $j$ 个挂钩的最大收益

由于挂钩的数量影响下一个挂饰能否被选择，而最外层又是循环挂饰，所以必须将挂饰按照挂钩数量从大到小排序

另外我们不需要存储超过 $n$ 个挂钩，所以我们将定义改为有大于等于 $j$ 个挂钩

时间复杂度 $O(n^2)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 2010
#define INF 1000000000
#define cn const node
using namespace std;

int n; 

int f[maxn][maxn];

struct node {
    int x, y;

    friend bool operator < (cn &u, cn &v) { return u.x > v.x; } 
} a[maxn];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1); 
    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < maxn; ++j) f[i][j] = -INF; 
    f[0][1] = 0; 
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j) 
            f[i][j] = max(f[i - 1][j], f[i - 1][max(j - a[i].x, 0) + 1] + a[i].y);
    int ans = 0;
    for (int i = 0; i <= n; ++i) ans = max(ans, f[n][i]);
    cout << ans << endl; 
    return 0;
}