题目链接
题目大意
你掉入了“垃圾井”,已知井的深度为 \(D\)
有 \(N\) 个垃圾,每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费时间。
现已知道了第 \(i\) 个垃圾扔下的时间 \(a[i].t\) ,以及每个垃圾堆放的高度 \(a[i].h\) 和吃进该垃圾能维持生命的时间 \(a[i].f\)
要求出最早能逃出井外的时间(假设你当前体内有足够持续 \(10\) 小时的能量,如果你 \(10\) 小时内没有进食,你就将饿死)
如果你可以爬出井,输出一个整数表示最早什么时候可以爬出;否则输出你最长可以存活多长时间。
解题思路
爬出井的时间一定是某个垃圾扔下的时间,所以我们无需对时间进行考虑
定义 \(dp[i][j][k]\) 表示第 \(i\) 个垃圾 , 垃圾堆积的高度为 \(j\) , 总共补充的的能量为 \(k\)
那么可得
\(dp[0][0][10] = true\)
\(dp[i - 1][j][k] = true?dp[i][j + a[i].h][k] = true,dp[i][j][k + a[i].f] = true\)
注意当 \(a[i].h + j >= D\)时,直接 \(return\) 并输出 \(a[i].t\) 即可
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int M = 1e2 + 10;
bool dp[M][M][30 * M];
struct node{
int t , f , h;
bool operator < (const node & b) const {
return t < b.t;
}
}a[M];
signed main()
{
int d , n , ma = 10;
cin >> d >> n;
for(int i = 1 ; i <= n ; i ++)
{
int t , f , h;
cin >> t >> f >> h;
a[i].t = t , a[i].f = f , a[i].h = h;
}
sort(a + 1 , a + 1 + n);
a[0].t = 0 , a[0].f = 0 , a[0].h = 0;
dp[0][0][10] = 1;
for(int i = 1 ; i <= n ; i ++)
{
int flag = 0;
for(int j = 0 ; j <= d - 1 ; j ++)
{
for(int k = a[i].t ; k <= 3000 ; k ++)
{
if(dp[i - 1][j][k])
{
dp[i][j + a[i].h][k] = true;
dp[i][j][k + a[i].f] = true;
flag = 1;
ma = max(ma , k + a[i].f);
if(j + a[i].h >= d) return cout << a[i].t << '\n' , 0;
}
}
}
if(!flag) return cout << ma << '\n' , 0;
}
cout << ma << '\n';
return 0;
}