ZR#998 柔光的暖阳◎ 2024-04-20 10:33 100阅读 0赞 ## ## 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; } 转载于:https://www.cnblogs.com/Repulser/p/11488171.html
相关 ZR#997 ZR\997 解法: > 找找规律就出来了,全场最简单的一道题。 CODE: include<iostream> include<cstdi... 怼烎@/ 2024年04月20日 10:34/ 0 赞/ 89 阅读
相关 ZR#999 ZR\999 解法: > 一道计数题,看到要求必须 $ m $ 个标号,所有标号至少出现一次的方案。 > 很容易想到可以容斥,但容斥这个东西是一种很神奇... 清疚/ 2024年04月20日 10:34/ 0 赞/ 85 阅读
相关 ZR#957 ZR\957 解法: > 首先 $ T $ 必须得要是 $ S $ 的子序列,不然不存在好的下标序列,因此一定无解。 > 考虑判断一个串 $ T $ 是... 痛定思痛。/ 2024年04月20日 10:34/ 0 赞/ 88 阅读
相关 ZR#959 ZR\959 解法: > 对于一个询问,设路径 $ (u, v) $ 经过的所有边的 $ gcd $ 为 $ g $,这可以倍增求出。 > 考虑 $ g... Bertha 。/ 2024年04月20日 10:34/ 0 赞/ 90 阅读
相关 ZR#998 ZR\998 解法: > 先把所有物品按照拿走的时间从小到大排序,拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。 ... 柔光的暖阳◎/ 2024年04月20日 10:33/ 0 赞/ 101 阅读
相关 ZR#954 分组 ZR\954 分组 解法: > 设 $ f\[i\]\[a\]\[b\] $ 表示考虑了排序后的前 $ i $ 个人,目前已经有 $ a $ 个组配好了,还... 分手后的思念是犯贱/ 2024年04月20日 10:32/ 0 赞/ 87 阅读
相关 ZR#956 集合 ZR\956 集合 解法: > 维护一个异或操作的懒标记,并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。 > 考虑一个数字 $ x $ 变为... 待我称王封你为后i/ 2024年04月20日 10:31/ 0 赞/ 80 阅读
相关 ZR#712 消灭砖块 题意: > 很多块砖分布在一个 $ m \\times m $ 的矩阵中,他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵... 朱雀/ 2024年04月20日 10:24/ 0 赞/ 76 阅读
相关 ZR#710 雷劈数 题意: > 现在给出两个整数,求出位于两个整数之间的所有的“雷劈数。 解法: > 因为雷劈数特殊的性质,所以在数据范围中的雷劈数实际很少,直... ゝ一纸荒年。/ 2024年04月20日 10:24/ 0 赞/ 96 阅读
相关 ZR#996 ZR\996 解法: > 若删除长度为 $ x $ 的子串后序列中没有相同元素,那么一定有至少一个长度为 $ x+1 $ 的子串,删除它后序列中也没有相同元... 怼烎@/ 2024年04月20日 10:23/ 0 赞/ 84 阅读
还没有评论,来说两句吧...