华师一附中OI组

标题: P1757 通天之分组背包 [打印本页]
作者: admin    时间: 2018-6-3 21:51
标题: P1757 通天之分组背包
https://www.luogu.org/problemnew/show/P1757

题目背景
直达通天路·小A历险记第二篇

题目描述
自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入输出格式
输入格式：
两个数m,n，表示一共有n件物品，总重量为m

接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数

输出格式：
一个数，最大的利用价值

输入输出样例
输入样例#1：
45 3
10 10 1
10 5 1
50 400 2
输出样例#1：
10
说明
1<=m<=1000 1<=n<=1000 组数t<=100
作者: 胡雨菲菲    时间: 2018-6-5 18:01
  1. #include <cstdio>
  2. #include <algorithm>
  3. typedef long long LL;
  4. using namespace std;

  6. const int N = 1010;
  7. const LL INF = 1ll << 62;

  9. struct A {
  10.     LL cost, val, group;
  11.     bool operator < (const A &x) {
  12.         return group < x.group;
  13.     }
  14. }a[N];

  16. struct Group {
  17.     LL s, t, small;
  18. }g[N];

  20. LL f[N];

  22. int main() {
  23.     LL V, n;
  24.     scanf("%lld%lld", &V, &n);
  25.     for(int i = 1; i <= n; i++) {
  26.         scanf("%lld%lld%lld", &a[i].cost, &a[i].val, &a[i].group);
  27.     }
  28.     sort(a + 1, a + n + 1);
  29.     for(int i = 1; i <= n; i++) {
  30.         if(a[i].group != a[i - 1].group) {
  31.             g[a[i].group].s = i;
  32.         }
  33.         g[a[i].group].t = i;
  34.     }
  35.     for(int i = 1; i <= a[n].group; i++) {
  36.         g[i].small = INF;
  37.         for(int j = g[i].s; j <= g[i].t; j++) {
  38.             g[i].small = min(g[i].small, a[j].cost);
  39.         }
  40.     }
  41.    
  42.     for(int k = 1; k <= a[n].group; k++) { /// k-th group
  43.         for(int i = V; i >= g[k].small; i--) { /// i V
  44.             for(int j = g[k].s; j <= g[k].t; j++) { /// j which
  45.                 if(i >= a[j].cost) {
  46.                     f[i] = max(f[i], f[i - a[j].cost] + a[j].val);
  47.                 }
  48.             }
  49.         }
  50.     }
  51.     LL ans = 0;
  52.     for(int i = 1; i <= V; i++) {
  53.         ans = max(ans, f[i]);
  54.     }
  55.     printf("%lld", ans);
  56.     return 0;
  57. }
复制代码
作者: 吴语林    时间: 2018-7-30 00:08
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. vector <int> v[1100],w[1100];
  14. int f[1100],m,n,T=0;
  15. int main()
  16. {
  17.     scanf("%d%d",&m,&n);
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         int v1,w1,a1;
  21.         scanf("%d%d%d",&w1,&v1,&a1);
  22.         v[a1].push_back(v1);
  23.         w[a1].push_back(w1);
  24.         T=max(T,a1);
  25.     }
  26.     for(int i=1;i<=T;i++)
  27.             for(int j=m;j>=0;j--)
  28.                     for(int k=0;k<v[i].size();k++)
  29.                             if(j>=w[i][k])
  30.                                     f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
  31.     printf("%d",f[m]);
  32.     return 0;
  33. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2