P1156-垃圾陷阱

Dear 丶 2023-06-01 08:52 30阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define MOD 1000000007
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 struct rubbish
    24 {
    25     int t;
    26     int f;
    27     int h;
    28     bool operator < (rubbish b)
    29     {
    30         return t < b.t;
    31     }
    32 };
    33 int D,G;
    34 rubbish a[103];
    35 int dp[103][103];
    36 int main()
    37 {
    38     D = read(), G = read();
    39     
    40     dp[0][0] = 10;
    41     _for(i,1,G+1)
    42         a[i].t = read(),a[i].f = read(),a[i].h = read();
    43     sort(a+1,a+G+1);
    44     _for(i,0,G)
    45         _for(j,0,D)
    46         {
    47             if(dp[i][j]>=a[i+1].t)
    48             {
    49                 int sm = j+a[i+1].h;
    50                 if(sm >= D)
    51                 {
    52                     write(a[i+1].t);
    53                     return 0;
    54                 }
    55                 dp[i+1][j] = max(dp[i+1][j],dp[i][j]+a[i+1].f);
    56                 dp[i+1][sm] = max(dp[i+1][sm],dp[i][j]);
    57             }
    58         }
    59     int rnt = INT_MIN;
    60     _for(i,1,G+1)
    61         rnt = max(rnt,dp[i][0]);
    62     write(rnt);
    63     return 0;
    64 }

转载于:https://www.cnblogs.com/Asurudo/p/11411982.html