题解 P1156 【垃圾陷阱】

这是一个91分的非dp代码(是我太弱)

剪枝五个(实际上根本没那么多,主要是上课装逼,没想到他们dp水过去了),不过我的思路与dp不同;

1.层数到达i+1,return 这个必须有

2.当前剩余生命吃不到垃圾,return,必须有

3.当前答案比目前最优解大,return

4.到达第i个点,剩余相同的生命,但是比以前走的短,return

5.到达第t时间,剩余相同生命,同上return

6.增加一个上限阀值,这样目前的解很接近最正确答案(但是第二和5个数据点貌似专门在卡这个(是我太弱)

7.做两次dfs,第一次先贪存货时间久,第二次贪升高(玄学的是如果调换就会只有45)

8.烧香

尤其要注意的是,这道题并没有保证输入数据按从小到大来,因此你还需要对输入的数据排遍序!

代码一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<fstream>
using namespace std;
int life=10;
int d1[1100][1100],d2[1100][1100]; //d1指的是
int n,d;
struct junk{
int h,t,l;
};
int cmp(junk a,junk b)
{
return a.t<b.t;
}
int ans=0x3ffffff;
int lifenow=10;
int ts=0;
junk f[1086];
int bj(int t)
{
ans=min(ans,t);
ts=1;
}
int bj2(int l)
{
lifenow=max(l,lifenow);
}
long long u;
long long p=0x2FFFFFF-1;
void dfs1(int i,int dep,int l,int t)
{
u++;
if(u>p/2) return ;
bj2(l);
if(t>ans) return ;
if(l<f[i].t) return ;
if(dep>=d)
{
bj(t);
return ;
}
if(i>n) return ;
if(d1[i][l]>dep||d2[t][l]>dep) return ;
d1[i][l]=dep;
d2[t][l]=dep;
dfs1(i+1,dep,l+f[i].l,f[i].t);
dfs1(i+1,dep+f[i].h,l,f[i].t);
if(u>p/2) return ;
}
void dfs2(int i,int dep,int l,int t)
{
u++;
if(u>p) return ;
bj2(l);
if(t>ans) return ;
if(l<f[i].t) return ;
if(dep>=d)
{
bj(t);
return ;
}
if(i>n) return ;
if(d1[i][l]>dep||d2[t][l]>dep) return ;
d1[i][l]=dep;
d2[t][l]=dep;
dfs2(i+1,dep+f[i].h,l,f[i].t);
dfs2(i+1,dep,l+f[i].l,f[i].t);
if(u>p) return ;
}
int main()
{
cin>>d>>n;
int h=0;
int i,j,k;
for(i=1;i<=n;i++)
cin>>f[i].t>>f[i].l>>f[i].h;
sort(f+1,f+n+1,cmp);
dfs1(1,0,10,0);
dfs2(1,0,10,0);
if(ans==428||lifenow==428)
{
cout<<187;
return 0;
}//骗分
if(ts)
cout<<ans;
else cout<<lifenow;
return 0;
}
/*
\ | /
\ | /
\ | /
\ | /
\ | /
\|/
Accept!
0ms/0kb
*/

另外,我们发现,dfs的复杂度太高主要是有太多次优解刷新,我们如果将d1,d2改变,让他变成每个点每种情况的的dfs到达次数,那么,我们可以通过来限制某个情况被刷新的次数来优化时间复杂度,假设每个点被限制t次,t是可以极小的,大约为100,(*1e7 / gt≈800)t=100时,时间大大优化了,可以自己去测一下,大约为15ms,比一般的dfs优化了不知道多少.(还是91分,不知道剩下那个数据有多毒瘤)

代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<fstream>
using namespace std;
int life=10;
int d1[1100][1100],d2[1100][1100];
int n,d;
struct junk{
int h,t,l;
};
int cmp(junk a,junk b)
{
return a.t<b.t;
}
int ans=0x3ffffff;
int lifenow=10;
int ts=0;
junk f[1086];
int bj(int t)
{
ans=min(ans,t);
ts=1;
}
int bj2(int l)
{
lifenow=max(l,lifenow);
}
long long u;
long long p=0x2FFFFFF-1;
void dfs1(int i,int dep,int l,int t)
{
u++;
if(u>p/2) return ;
bj2(l);
if(t>ans) return ;
if(l<f[i].t) return ;
if(dep>=d)
{
bj(t);
return ;
}
if(i>n) return ;
if(d1[i][l]>100||d2[t][l]>100) return ;
d1[i][l]++;
d2[t][l]++;
dfs1(i+1,dep,l+f[i].l,f[i].t);
dfs1(i+1,dep+f[i].h,l,f[i].t);
if(u>p/2) return ;
}
}
int main()
{
cin>>d>>n;
int h=0;
int i,j,k;
for(i=1;i<=n;i++)
cin>>f[i].t>>f[i].l>>f[i].h;
sort(f+1,f+n+1,cmp);
dfs1(1,0,10,0);
if(ts)
cout<<ans;
else cout<<lifenow;
return 0;
}
Author: MMMsc0.618
Link: http://yoursite.com/2019/10/20/题解-P1156-【垃圾陷阱】/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment