ZR#998-蒲公英云

ZR#998

#

ZR#998

解法：

先把所有物品按照拿走的时间从小到大排序，拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。
考虑 $ dp $ ，设 $ f[i][j] $ 表示 $ i $ 以及 $ i $ 上面物品在所有时刻中最大重量为 $ j $ 时的最大收益。
转移的时候，我们需要枚举所有 $ i $ 上面的物品，维护一个 $ g[i] $ 表示时刻 $ i $ 之前物品的最大收益是多少。然后直接转移就好了。

CODE:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long #define N 100010 struct Node { int in,out; int w,s,v; inline bool operator < (const Node &x) const { if(in != x.in) return in < x.in; else return out > x.out; } } a[N]; int f[1010][2010],n,ans,s; int main() { scanf("%d%d",&n,&s); for(int i = 1 ; i <= n ; i++) scanf("%d%d%d%d%d",&a[i].in,&a[i].out,&a[i].w,&a[i].s,&a[i].v); sort(a + 1,a + n + 1); for(int i = 1 ; i <= n ; i++) { int u = min(s,a[i].s); for(int j = 0 ; j <= u ; j++) { f[i][j] = a[i].v; int sum = 0; for(int k = i - 1 ; k >= 1 ; k--) { if(a[k].out >= a[i].out) f[i][j] = max(f[i][j],f[k][j + a[i].w] + a[i].v + sum); if(a[k].out <= a[i].in && a[k].s <= j + a[i].w) sum += a[k].v; } ans = max(ans,f[i][j]); } } printf("%d \n",ans); //system("pause"); return 0; }

补充，因为写完题解就被叉了，所以补一发改过后的。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long #define N 1010 struct bag { int in, out; int w, s, v; } d[N]; int n,S,f[N][N],g[N][N]; inline bool cmp(bag a, bag b) { if (a.out == b.out)return a.in > b.in; else return a.out < b.out; } int main() { scanf("%d%d",&n,&S); for(int i = 1 ; i <= n ; i++) scanf("%d%d%d%d%d",&d[i].in,&d[i].out,&d[i].w,&d[i].s,&d[i].v); d[0].out = 2 * n + 1,d[0].s = S; sort(d,d + n + 1,cmp); for(int i = 0 ; i <= n ; i++) { int j = 0, t = min(d[i].s, S - d[i].w); memset(g,0,sizeof(g)); while(d[j].out <= d[i].in) j++; for(int k = d[i].in + 1 ; k <= d[i].out ; k++) { memcpy(g[k],g[k-1],sizeof(g[k])); while(j < i && d[j].out == k) { if(d[j].in < d[i].in) { j++; continue; } for(int l = 0 ; l <= t ; l++) g[k][l] = max(g[k][l], g[d[j].in][l] + f[j][l]); j++; } } for(int k = 0 ; k <= t ; k++) f[i][k + d[i].w] = g[d[i].out][k] + d[i].v; for(int k = 1 ; k <= S ; k++) f[i][k] = max(f[i][k], f[i][k - 1]); } printf("%d\n", f[n][S]); //system("pause"); return 0; }