AT_dp_x 题解

SkyRainWind · 2023-01-30 17:07:23 · 题解

做法和其它题解略有不同，来写一发

首先肯定考虑将 \{w,s,v\} 排序，如何排序呢？考虑 i 在 j 上面和下面的时候，还能剩下的空间。

当 i 比 j 更优的时候，i 需要放在 j 前面，也就是在下面，因此此时 cap_2>cap_1 这就是排序的准则。

排完序之后用一个类似背包的写法：dp_{i,s} 表示考虑到前 i 个块，当前剩余容量为 s 的最大价值。转移就考虑是否放当前块：dp_{i,min(j-w_i,s_i)} \leftarrow dp_{i-1,j}+v_i。

一个细节：如何判断当前放的块是第一块？首先可以把第二维开大到 20000，这样足够转移的，或者是将一开始不合法的状态都赋成负无穷大，然后每次转移。

这里放第二种写法的代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn=20005;

int n;
struct node{int w,s,v;}a[maxn];
int cmp(node i,node j){return min(j.s,i.s-j.w) > min(i.s,j.s-i.w);}
ll dp[1005][20005];
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].w,&a[i].s,&a[i].v);
    sort(a+1,a+n+1,cmp);

    for(int i=0;i<=10000;i++)dp[1][i] = -1e18;
    dp[1][a[1].s] = a[1].v;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=10000;j++)dp[i][j] = dp[i-1][j];
        dp[i][a[i].s] = max(dp[i][a[i].s], 1ll*a[i].v);
        for(int j=a[i].w;j<=10000;j++){
            ll &dd = dp[i][min(j-a[i].w, a[i].s)];
            dd = max(dd, dp[i-1][j] + a[i].v);
        }
    }
    ll ans=0;
    for(int i=0;i<=10000;i++)ans = max(ans, dp[n][i]);
    cout<<ans<<'\n';

    return 0;
}