这是一个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
67
| #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;
}
|
