P4138 [JOISC2014] 挂饰

XP3301_Pipi · 2024-04-27 09:45:58 · 题解

题解区中没有刷表法的做法，也就是从第 i 阶段转移到第 i+1 阶段。自我感觉这种方法更方便，且不易出错。

可以把 a_i 看作容量，把 b_i 看作价值，这道题就变成了背包容量可以扩张的问题。
不过直接做背包会出现一些问题：

由于第 i 个挂件只能由前 i-1 个挂件转移而来，但是可能先挂 i 后面挂钩更多的再挂 i 更优，看上去似乎有后效性，无法直接转移。
Solution：贪心思想，把挂件按 a_i 排序，让挂钩更多的排在前面。
Proof：邻项交换法。设选出挂件集合中含有 i 和 j，并假设 a_i<a_j，当 i<j 时，由于我们的 dp 是按挂件序号划分阶段的，这就导致从 i+1 到 j-1 的挂件只能再选 a_i-1 个；当 j<i 时，从 j+1 到 i-1 能再选 a_j-1 个。显然 j>i 时可选的挂件更多。
挂件数量为 N，那么挂钩大于 N 是没有意义的，所以 dp 中当挂钩过多时直接强行认为是 N 就可以了。

接下来就是 DP 的转移方程：
设 dp_{i,j} 为考虑到第 i 个挂件，当前空闲挂钩数量为 j 时的最大喜悦值。
考虑刷表法：

dp_{i+1,k}=\max(dp_{i+1,k},dp_{i,k},dp_{i,j}+b_{i+1})

其中：

k=j+a_{i+1}-1

也就是分为两种情况，第 i+1 个挂件选还是不选。
当 j+a_{i+1}-1>N 时，就将其认为是 N。

代码如下：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
const int N=2015;
const long long INF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

template<typename Type>
inline void read(Type& res) {
    Type x=0,f=1;
    char c=' ';
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    res=x*f;
}

#define x first
#define y second

pii a[N];
ll dp[N][N],ans;
int n;

signed main() {
//  不开longlong见祖宗！
//  检查数组大小！
//  禁止在int乘int时不开longlong！
//  注意输出格式！ 
//  STL数据类型拷贝赋值时间复杂度是 O(N)！
//  读入单个字符要用字符串，防毒瘤数据！
//  (1<<63)爆ll，(1<<31)爆int！
//  比赛结束前5min，检查上述7项，并编译运行！！！！！ 
//  -std=c++14 -O2 -Wall -Wextra -Wshadow
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i].x);
        read(a[i].y);
    }
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    memset(dp,-0x3f,sizeof(dp));
    dp[0][1]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            int k=min(n,j+a[i+1].x-1);
            dp[i+1][k]=max(dp[i+1][k],max(dp[i][j]+a[i+1].y,dp[i][k]));
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}