垃圾陷阱

发表于 更新于 分类于

Problems Website

  • 垃圾陷阱

    Solution

  • 一道背包题目，可以用二维解，但有一种比较神奇的状态，我们设f[i]为高度i时卡门的生命，这样就变成了一个01背包，决策无疑只有吃垃圾或垫垃圾。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    using namespace std;
    int sc() {
    	int xx = 0, ff = 1; char cch = gc;
    	while(cch < '0' || cch > '9') {
    		if(cch == '-') ff = -1; cch = gc;
    	}
    	while(cch >= '0' && cch <= '9') {
    		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    	}
    	return xx * ff;
    }
    struct node {
    	int t, l, h;
    	bool operator < (const node &x) const {
    		return t < x.t;
    	}
    }a[110];
    int d, g;
    int f[110]; //f[high] = life
    int main() {
    	d = sc(); g = sc();
    	for(int i = 1; i <= g; i++) {
    		a[i].t = sc();
    		a[i].l = sc();
    		a[i].h = sc();
    	}
    	sort(a + 1, a + 1 + g);
    	memset(f, -1, sizeof(f));
    	f[0] = 10;
    	for(int i = 1; i <= g; i++) {
    		for(int j = d; j >=0; j--) {
    			if(f[j] >= a[i].t) {
    				if(j + a[i].h >= d) {
    					printf("%d\n", a[i].t);
    					return 0;
    				}
    				f[j + a[i].h] = max(f[j], f[j + a[i].h]);
    				f[j] += a[i].l;
    			}
    		}
    	}
    	printf("%d\n", f[0]);
    	return 0;
    }

rp++