终于搞懂这个题怎么写了
- 首先这个题目有好想却不那么好写$O(GD \Sigma f)$的写法,按照洛谷以前的速度是可以AC的,现在在别的oj也可以卡着将近1000ms通过,但是洛谷过不了了233
思路很简单:考虑“看题说话”,把题目里面的相关量都加入状态。
状态转移方程:其中$f(i,j,k)$表示状态为第i个辣鸡,当前处在高度j,剩余的生命长度为k。$\Delta T$代表这个垃圾和下个垃圾之间的时间差。
$$
f(i,j,k)=
\begin{cases}
t_i & \text{ 如果 } j+h_i \geq d \\
\min \begin {cases}
f(i+1,j,k+f_i- \Delta T) & \text { 如果 } k+f_i \geq \Delta T \\
f(i+1,j+h_i,k-\Delta T) & \text { 如果 } k \geq \Delta T \\
\infty & \text { 若不满足上述 }
\end{cases}
& \text{ 如果 } j+h_i < d
\end{cases}
$$
这样求出的就是最短的爬上去的时间,然后如果不可能爬上去的话就只吃垃圾不放垃圾就行了
- 然后就是$O(GD)$的解法了,我对着网上各种刷表法的题解懵逼了很久,所以这里给出一种基于填表的解法
考虑第i个辣鸡,我们有两种选择,吃掉和堆起来。令$g(i,j)$代表处理到了第i个物品,在高度j的最大死亡时刻。
于是显然可以从$g(i-1,j-h_i)$与$g(i-1,j)$转移而来。
方程如下:
$$
g(i,j)=
\begin{cases}
g(i-1,j-h_i)& \text{ 如果 } j \geq h_i \text{且} g(i-1,j-h_i) \geq t_i \\
g(i-1,j)+f_i& \text{ 如果 } g(i-1,j) \geq t_i \\
g(i-1,j)& \text{ 若不满足上述 }
\end{cases}
$$
实际上可以采用滚动数组省去$g(i,j)$的第一维
最后上代码:
Solution 1:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Item{
int t,f,h;
bool operator<(const Item& it){
return t<it.t;
}
};
const int MAXG=100,MAXD=100,INF=1e9;
int D,G,opt[MAXG+1][MAXD+1][3011];
Item P[MAXG+10];
int main(){
scanf("%d%d",&D,&G);
for(int i=1;i<=G;i++)
scanf("%d%d%d",&P[i].t,&P[i].f,&P[i].h);
sort(P+1,P+G+1);
P[G+1].t=(INF<<1);
for(int i=G;i>=1;i--)
for(int j=D-1;j>=0;j--)
for(int k=0;k<=3010;k++) {
int Tm=P[i+1].t-P[i].t;
if(j+P[i].h>=D) opt[i][j][k]=P[i].t;
else{
opt[i][j][k]=(INF<<1);
if(k+P[i].f>=Tm)
opt[i][j][k]=min(opt[i][j][k],opt[i+1][j][k+P[i].f-Tm]);
if(k>=Tm)
opt[i][j][k]=min(opt[i][j][k],opt[i+1][j+P[i].h][k-Tm]);
}
}
if(P[1].t>10) printf("10\n");
else {
if(opt[1][0][10-P[1].t]<INF-10) printf("%d\n",opt[1][0][10-P[1].t]);
else {
int k=10-P[1].t;
for(int i=1;i<=G;i++) {
static int Tm;
Tm=P[i+1].t-P[i].t;
if(k+P[i].f<Tm) {
printf("%d\n",P[i].t+k+P[i].f);
return 0;
} else
k=k+P[i].f-Tm;
}
}
}
return 0;
}
Solution 2:
#include <cstdio>
#include <algorithm>
using namespace std;
struct Garbage{ int t,f,h; };
const int MAXD=100, MAXG=100, MAXH=25;
const int INF=0x3f3f3f3f;
int D,G,p1,p2,tot,opt[(MAXD+MAXG*MAXH)<<1];
Garbage P[MAXG+10];
bool cmp(const Garbage& x,const Garbage& y) { return x.t<y.t; }
int main(){
scanf("%d%d", &D, &G);
tot=D;
for(int i=1;i<=G;i++){
scanf("%d%d%d", &P[i].t, &P[i].f, &P[i].h);
tot+=P[i].h;
}
sort(P+1,P+G+1,cmp);
opt[0]=10;
for(int i=1;i<=G;i++)
for(int j=tot;j>=0;j--) {
p1=p2=0;
if(j>=P[i].h && opt[j-P[i].h]>=P[i].t) p1=opt[j-P[i].h];
if(opt[j]>=P[i].t) p2=opt[j]+P[i].f;
if(p1!=0 || p2!=0)
opt[j]=max(p1,p2);//上述条件都不满足时,p1=p2=0,应该让opt[j]保持原样
//为何不设置为0呢?考虑一下opt[0]就知道了。假设只有一个物品在11s时掉落。
if(j>=D && opt[j]!=0) {
printf("%d\n",P[i].t);
return 0;
}
}
printf("%d\n",opt[0]);
}