[Codeforces 864E]Fire-白红宇

[Codeforces 864E]Fire

阅读量：5010 次

发布时间：2019-06-12

本文共 4032 字，大约阅读时间需要 13 分钟。

Description

Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take tiseconds to save i-th item. In addition, for each item, he estimated the value of di — the moment after which the item i will be completely burned and will no longer be valuable for him at all. In particular, if ti ≥ di, then i-th item cannot be saved.

Given the values pi for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item a first, and then item b, then the item a will be saved in ta seconds, and the item b — in ta + tb seconds after fire started.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of items in Polycarp's house.

Each of the following n lines contains three integers ti, di, pi (1 ≤ ti ≤ 20, 1 ≤ di ≤ 2 000, 1 ≤ pi ≤ 20) — the time needed to save the item i, the time after which the item i will burn completely and the value of item i.

Output

In the first line print the maximum possible total value of the set of saved items. In the second line print one integer m — the number of items in the desired set. In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.

Sample Input

3 3 7 4 2 6 5 3 7 6

Sample Output

11 2 2 3

HINT

In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2seconds. Thus, the total value of the saved items will be 6 + 5 = 11.

题解

交这道题的时候，正好碰到$codeforces$被卡测评...等了（翻.墙逛P站逛了）好久...

首先我们考虑这样一个问题，我们救物品如果没有烧毁时间，无论先救什么都可以，但既然有烧毁时间，那是不是越先烧毁的就越需要先救。

我们按$d$值从小到大排序（这种基于排序的背包之前做过一道：。至于为什么要排序，思路差不多，不懂的可以戳回去看看），然后做朴素的背包。

由于要输出路径，$dp$数组我们必须多开一维，令$f[i][j]$表示选到排完序后的$i$号物品时结束时间为$j$的可能的最大价值：

$f[i][j] = Max(f[i-1][j], f[i-1][j-a[i].t]+a[i].p)$，注意边界情况。

另外特别要注意的是，对于$d$的解释：即若救$i$号物品，那么一定要在时刻$d_i$之前完成。

1 //It is made by Awson on 2017.9.29 2 #include 
     
       3 #include 
       4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define LL long long16 #define Max(a, b) ((a) > (b) ? (a) : (b))17 #define Min(a, b) ((a) < (b) ? (a) : (b))18 #define sqr(x) ((x)*(x))19 #define lowbit(x) ((x)&(-(x)))20 using namespace std;21 void read(int &x) {22 char ch; bool flag = 0;23 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());24 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());25 x *= 1-2*flag;26 }27 28 struct item {29 int t, d, p, id;30 bool operator < (const item &b) const{31 return d < b.d;32 }33 }a[105];34 int n, maxd;35 int f[105][2005];36 int pre[105][2005];37 38 void print(int i, int j, int cnt) {39 if (i == 0) {40 printf("%d\n", cnt);41 return;42 }43 if (pre[i][j] == j) print(i-1, j, cnt);44 else {45 print(i-1, pre[i][j], cnt+1);46 printf("%d ", a[i].id);47 }48 }49 void work() {50 read(n);51 for (int i = 1; i <= n; i++) {52 read(a[i].t), read(a[i].d), read(a[i].p);53 a[i].id = i;54 maxd = Max(maxd, a[i].d);55 }56 sort(a+1, a+1+n);57 for (int i = 1; i <= n; i++)58 for (int j = 0; j <= maxd; j++) {59 f[i][j] = f[i-1][j];60 pre[i][j] = j;61 if (j >= a[i].t && j < a[i].d)62 if (f[i-1][j-a[i].t]+a[i].p > f[i][j]) {63 f[i][j] = f[i-1][j-a[i].t]+a[i].p;64 pre[i][j] = j-a[i].t;65 }66 }67 int loc = 0, ans = 0;68 for (int i = 0; i < maxd; i++) {69 if (f[n][i] > ans) {70 ans = f[n][i];71 loc = i;72 }73 }74 printf("%d\n", ans);75 print(n, loc, 0);76 }77 int main() {78 work();79 return 0;80 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7610987.html

你可能感兴趣的文章