pascal DP(动规)垃圾陷阱(要写出状态的意义,给方程)(每步解析+10)
发布网友
发布时间：2024-10-01 10:43
共1个回答
热心网友
时间：2024-11-24 19:05
a[k,i,j]表示取第k个垃圾时,
高度i，总生命值j(即从时间0到现在一直累加所得的)的状态能否得到。
若a[k-1][i][j]=true，
则f[k][i+h[k]][j]=true;
f[k][i][j+f[k]]=true;
(j>=t[k])
若i+h[k]>=d,则已经可以出去，输出时间t[k]即可。
如果达不到，则吃掉所有垃圾，得到最大存活时间。
初始值f[0][0][10]=true
降维处理
因为当前的状态只与上一层状态相关，所以3维可以降为2维。
