2020-09-27 03:32:34 亲,请 登录 或者 注册
新闻主页 国内新闻 国外新闻 民生资讯 社会动态 各地新闻 经济资讯 时证要闻
 
当前位置:: 瞬间新闻网 >> 经济资讯 >> 垃圾陷阱(动态规划) 内容
垃圾陷阱(动态规划)
来源:瞬间新闻网 时间:2018-08-27   点击发表评论


版权声明:本文为作者原创,若转载请注明地址。https://blog.csdn.net/chenxiaoran666/article/details/81977767
点此看题面

大致题意:一只奶牛掉进了一个垃圾陷阱里,每个垃圾有三个属性:被扔下来的时间Ti"role="presentation">TiTi,吃了能够延长的生命时间Fi"role="presentation">FiFi,叠起来的高度Hi"role="presentation">HiHi。每一个垃圾可以用来吃或叠,如果某一时刻垃圾叠起来的总高度大于等于M"role="presentation">MM,奶牛就可以离开这个陷阱。已知奶牛一开始能够存活10个单位时间,问你它离开陷阱最少所需的时间。如果它无论如何都无法离开陷阱,就输出它最多能够存活的时间。



这题应该比较显然是一道DP"role="presentation">DPDP题。

首先要注意先将垃圾按照扔下来的时间Ti"role="presentation">TiTi排序。

我们可以用fi,j"role="presentation">fi,jfi,j表示当前扔下了第i"role="presentation">ii个垃圾,叠起来的总高度为j"role="presentation">jj时还能存活的最大单位时间。

我们可以用fx,y=#x2212;1"role="presentation">fx,y=?1fx,y=?1来表示这种情况不存在。

那么依据题意,初始化时f0,0=10,f0,1...M=#x2212;1"role="presentation">f0,0=10,f0,1...M=?1f0,0=10,f0,1...M=?1.

由于一个垃圾有两种用途,因此我们可以分类讨论第i#x2212;1"role="presentation">i?1i?1个垃圾的用途:


吃:fi,j=fi#x2212;1,j+Fi#x2212;1#x2212;(Ti#x2212;Ti#x2212;1)"role="presentation">fi,j=fi?1,j+Fi?1?(Ti?Ti?1)fi,j=fi?1,j+Fi?1?(Ti?Ti?1)
叠:fi,j=fi#x2212;1,j#x2212;Hi#x2212;1#x2212;(Ti#x2212;Ti#x2212;1)"role="presentation">fi,j=fi?1,j?Hi?1?(Ti?Ti?1)fi,j=fi?1,j?Hi?1?(Ti?Ti?1)


整理一下,就可以得出转移方程:fi,j=max(fi#x2212;1,j+Fi#x2212;1,fi#x2212;1,j#x2212;Hi#x2212;1)#x2212;(Ti#x2212;Ti#x2212;1)"role="presentation">fi,j=max(fi?1,j+Fi?1,fi?1,j?Hi?1)?(Ti?Ti?1)fi,j=max(fi?1,j+Fi?1,fi?1,j?Hi?1)?(Ti?Ti?1)

不难发现,若fi,j#x2260;#x2212;1"role="presentation">fi,j≠?1fi,j≠?1且j+Hi#x2265;M"role="presentation">j+Hi≥Mj+Hi≥M,就可以直接输出Ti"role="presentation">TiTi并结束程序了。

这就是针对第一种情况的解法。



第二种情况的解法是建立在第一种情况的DP"role="presentation">DPDP的基础之上的。

可以看出,如果fi,j"role="presentation">fi,jfi,j不为0,那么奶牛还能活的时间最大为fi,j+Fi"role="presentation">fi,j+Fifi,j+Fi(吃掉当前的垃圾),那么总共能活的时间就是fi,j+Ti+Fi"role="presentation">fi,j+Ti+Fifi,j+Ti+Fi。

不难发现,只要fi,0+Ti+Fi"role="presentation">fi,0+Ti+Fifi,0+Ti+Fi不为#x2212;1"role="presentation">?1?1,它肯定大于fi,x+Ti+Fi(0x#x2264;M)"role="presentation">fi,x+Ti+Fi(0x≤M)fi,x+Ti+Fi(0x≤M)和fy,0+Ty+Fy(0#x2264;yi)"role="presentation">fy,0+Ty+Fy(0≤yi)fy,0+Ty+Fy(0≤yi)的,因此,我们只要求出最大的满足fi,0#x2260;#x2212;1"role="presentation">fi,0≠?1fi,0≠?1的i"role="presentation">ii,答案就是此时的fi,0+Ti+Fi"role="presentation">fi,0+Ti+Fifi,0+Ti+Fi。


#defineswap(x,y)(x^=y,y^=x,x^=y)
#definetc()(A==B(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)
#definepc(ch)(pp_100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))
#defineN100
#defineM100
intpp_=0;charff[100000],*A=ff,*B=ff,pp[100000];
usingnamespacestd;
intn,m,f[N+5][M+5];
structlitter
intt,h,v;
}a[N+5];
inlinevoidread(intx)
x=0;intf=1;staticcharch;
while(!isdigit(ch=tc()))f=ch^'-'?1:-1;
while(x=(x3)+(x1)+ch-48,isdigit(ch=tc()));
x*=f;
inlinevoidwrite(intx)
if(x0)pc('-'),x=-x;
if(x9)write(x/10);
pc(x%10+'0');
inlineboolcmp(litterx,littery)//将垃圾按照扔下来的时间排序
returnx.t
intmain()
registerinti,j,ans=0;
for(read(m),read(n),i=1;i++i)read(a[i].t),read(a[i].v),read(a[i].h);
for(f[0][0]=10,i=1;i++i)f[0][i]=-1;//初始化
for(sort(a+1,a+n+1,cmp),i=1;i++i)//DP的核心代码
for(j=0;j++j)
if((f[i-1][j]0||f[i-1][j]+a[i-1].va[i].t-a[i-1].t)((j=a[i-1].h?f[i-1][j-a[i-1].h]:-1)a[i].t-a[i-1].t)){f[i][j]=-1;continue;}//如果当前状态无法转移到,就将f[i][j]赋值为-1,并跳过
if(j+a[i].h=m)returnwrite(a[i].t),fwrite(pp,1,pp_,stdout),0;//如果将当前垃圾叠起来的总高度大于m,就输出当前垃圾被扔下来的时间并退出程序
f[i][j]=max((j=a[i-1].h?f[i-1][j-a[i-1].h]:-1),(f[i-1][j]=0?f[i-1][j]+a[i-1].v:0))-(a[i].t-a[i-1].t);//求出f[i][j]
for(i=1;i++i)if(~f[i][0])ans=f[i][0]+a[i].t+a[i].v;elsebreak;//求出最大的满足f[i][0]≠-1的i,答案就是此时的f[i][0]+T[i]+F[i]
returnwrite(ans),fwrite(pp,1,pp_,stdout),0;
}

洛谷P1156垃圾陷阱背包DP">洛谷P1156垃圾陷阱背包DP
YihAN_Z

08-071064

题目大意:一头牛被困在一个初始为空的垃圾坑里,之后会扔下一些垃圾。每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费时间。这头牛开始时有足够持续10小时的能量,给定一些垃圾扔下的时间、高度与吃掉能提供的...


垃圾陷阱">【解题报告】垃圾陷阱
40079933.jpg"alt="qq_40079933">qq_40079933

02-2765

这道题是一道非常典型的DP,下面我们就来对这道题进行一些讲解!题目链接:P1156垃圾陷阱作为一道“提高+/省选-”的题目,相信这道题还是很有价值的,本题的价值就在“时间”这个限制变量...


洛谷1156垃圾陷阱">洛谷1156垃圾陷阱
KenxHe

11-04134

题目描述卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2...


洛谷1156垃圾陷阱">洛谷1156垃圾陷阱
hahalidaxin

03-30369

洛谷1156垃圾陷阱本题地址:?http://www.luogu.org/problem/show?pid=1156题目描述卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落...


动态规划#codevs1684洛谷1156垃圾陷阱">#动态规划#codevs1684洛谷1156垃圾陷阱
sugar_free_mint

07-2354

题目一个深ddd英尺的井,某犇掉进去,可以通过吃垃圾补充能量或者垫垃圾增高,问最早什么时候可以爬出,否则该犇最多存活多长时间。分析可以按垃圾的时间排序,然后设dp[height]d...


洛谷|动态规划|P1156垃圾陷阱">|洛谷|动态规划|P1156垃圾陷阱
Darost

10-03457

http://www.luogu.org/problem/show?pid=1156用布尔数组f[i][j]表示高度为i时体力值为j时的状态存在然后DP即可#include#includ...


垃圾陷阱洛谷1156dp">垃圾陷阱洛谷1156dp
A_loud_name

01-22197

题目描述卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2...


洛谷1156垃圾陷阱dp">洛谷1156垃圾陷阱dp
Loi_a

11-03295

https://www.luogu.org/problem/show?pid=1156这个题状态有很多种表示方法:1.f[i]表示堆到i的高度时最大生命值是多少。堆f[i+a[j...


洛谷1156垃圾陷阱(背包动规)">洛谷1156垃圾陷阱(背包动规)
LZJ209

08-071214

题目描述:卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2卡门想把垃圾堆起来,等到堆得与井同样高时,她就...


洛谷提高试炼场-动态规划篇的爆破">对于洛谷提高试炼场-动态规划篇的爆破
litble

11-05445

题外话由于本蒟蒻的动态规划实在是太弱啦,所以有必要爆破一下洛谷提高试炼常里面有很多非常好,难度也合适的动态规划题……(然而你还是抄了不少题解)niconiconi!让我们一起开始爆破吧。...





 
推荐新闻
 
 
手机浏览
瞬间新闻网 Total 0.030351(s) query 7, 报料QQ:点击这里给我发消息