设计招聘专业网站,中国机械网官网,网站改版策划书,洛谷网站中小玉文具怎么做垃圾陷阱
题目描述
卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方#xff0c;它的深度为 D D D#xff08; 2 ≤ D ≤ 100 2 \le D \le 100 2≤D≤100#xff09;英尺。
卡门想把垃圾堆起来#xff0c…垃圾陷阱
题目描述
卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方它的深度为 D D D 2 ≤ D ≤ 100 2 \le D \le 100 2≤D≤100英尺。
卡门想把垃圾堆起来等到堆得与井同样高时她就能逃出井外了。另外卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间 t t t 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000以及每个垃圾堆放的高度 h h h 1 ≤ h ≤ 25 1 \le h \le 25 1≤h≤25和吃进该垃圾能维持生命的时间 f f f 1 ≤ f ≤ 30 1 \le f \le 30 1≤f≤30要求出卡门最早能逃出井外的时间假设卡门当前体内有足够持续 10 10 10 小时的能量如果卡门 10 10 10 小时内不含 10 10 10 小时维持生命的时间同没有进食卡门就将饿死。
输入格式
第一行为两个整数 D D D 和 G G G 1 ≤ G ≤ 100 1 \le G \le 100 1≤G≤100 G G G 为被投入井的垃圾的数量。
第二到第 G 1 G1 G1 行每行包括三个整数 T T T 1 ≤ T ≤ 1000 1 \le T \le 1000 1≤T≤1000表示垃圾被投进井中的时间 F F F 1 ≤ F ≤ 30 1 \le F \le 30 1≤F≤30表示该垃圾能维持卡门生命的时间和 H H H 1 ≤ H ≤ 25 1 \le H \le 25 1≤H≤25该垃圾能垫高的高度。
输出格式
如果卡门可以爬出陷阱输出一个整数表示最早什么时候可以爬出否则输出卡门最长可以存活多长时间。
样例 #1
样例输入 #1
20 4
5 4 9
9 3 2
12 6 10
13 1 1样例输出 #1
13提示
【样例说明】
卡门堆放她收到的第一个垃圾 h e i g h t 9 \mathrm{height}9 height9
卡门吃掉她收到的第 2 2 2 个垃圾使她的生命从 10 10 10 小时延伸到 13 13 13 小时
卡门堆放第 3 3 3 个垃圾 h e i g h t 19 \mathrm{height}19 height19
卡门堆放第 4 4 4 个垃圾 h e i g h t 20 \mathrm{height}20 height20。
大致思路
分析题目我们需要求的答案是时间于是很自然而然的想到j描述高度或生命而dp数组存放时间。很显然这样状态既不完整也写不出转移方程。而且dp数组存的是当前状态下最大或最小的价值似乎也不满足。
这时候我们发现有4个值可能成为状态高度生命物品和时间难道要dp三维的吗
再分析题目每个垃圾都有一个下落的时间奶牛一定是在垃圾丢下来的时间就处理垃圾的可以得出这样的最优的那么物品就可以和时间关联起来了。这时候我们可以把时间仅仅当作干扰量给剔除了。
需要注意的是物品的使用顺序并不是随意的必须按它们下落的时间顺序来先后处理。这里排一下序即可
那么j代表什么呢
一下子我们并不能得出答案。先尝试dp[i][j]dp[i][j]代表前i件物品处理后在j血量时达到的最大高度。
值得一提的是j血量表示奶牛在暂时不考虑时间时所得到的最大血量
据说这个是叫离线
试着写一下它的状态转移方程 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] t r a s h [ i ] . h , d p [ i − 1 ] [ j t r a s h [ i ] . c ] ) dp[i][j]max(dp[i-1][j]trash[i].h,dp[i-1][jtrash[i].c]) dp[i][j]max(dp[i−1][j]trash[i].h,dp[i−1][jtrash[i].c])
发现这是对的然而我们再想想在关于j的一重循环里面对j的取值我们似乎并不好判断甚至要枚举很大。
所以我们再尝试讨论dp[i][j]dp[i][j]代表前i件物品处理后在h高度时达到的最大血量。
状态转移 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] t r a s h [ i ] . c , d p [ i − 1 ] [ j − t r a s h [ i ] . h ] ) dp[i][j]max(dp[i-1][j]trash[i].c,dp[i-1][j-trash[i].h]) dp[i][j]max(dp[i−1][j]trash[i].c,dp[i−1][j−trash[i].h])
发现这样也是对的而且j枚举起来也比较方便于是我们选择这种算法。
AC CODE
#includebits/stdc.h
using namespace std;
int d,g;
struct node{int tim,sur,high;
}a[555];
int f[555];
bool cmp(node aa,node bb){return aa.timbb.tim;
}
int main(){cindg;for(int i1;ig;i){cina[i].tima[i].sura[i].high;}sort(a1,a1g,cmp);f[0]10;for(int i1;ig;i){for(int jd;j0;j--){if(f[j]a[i].tim){if(ja[i].highd){couta[i].tim;return 0;}f[ja[i].high]max(f[j],f[ja[i].high]);f[j]a[i].sur;}}}coutf[0];return 0;
}洛谷题解区
附封面你的名字
