可爱精灵宝贝（贪心，搜索）

本文主要是介绍可爱精灵宝贝（贪心，搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

带有贪心思想的搜索，

我们很容易想到，对于自身来说，如果L---R区间已经走过，那么在最优策略下不会重复走

同时，每次我们都会找离本节点最近的点&&符合条件移动，

（假设我们当前不走，那么我们走到其他点才返回一定不优）

那么我们搜索的时间复杂度最大为2^100,又因为剪枝(L,R距离剪枝)，是能水掉的啦啦啦...

当然用DP做也行，我考试为啥要打状压？？？？？？？？？？？？

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<set>
 8 #include<vector>
 9 #include<map>
10 #include<queue>
11 #define MAXN 6101
12 #define int long long
13 using namespace std;
14 int a[MAXN],b[MAXN],t[MAXN];
15 int dis[MAXN][MAXN];
16 int n,k,m;
17 int sum=0;
18 void find(int pos,int l,int r,int time,int ans)
19 {
20      sum=max(ans,sum);
21      if(time>2000)return ;
22      //printf("pos=%lld l=%lld r=%lld time=%lld ans=%lld\n",pos,l,r,time,ans);
23      for(int i=pos-1;i>=1;--i)
24      {
25          if(a[i]>=l&&a[i]<=r)continue;
26          if(dis[pos][i]+time>t[i])continue;
27          find(i,min(a[i],l),max(r,a[i]),time+dis[pos][i],ans+b[i]);
28          break;
29      }
30      for(int i=pos+1;i<=m;++i)
31      {
32          if(a[i]>=l&&a[i]<=r)continue;
33          if(dis[pos][i]+time>t[i])continue;
34          find(i,min(l,a[i]),max(a[i],r),time+dis[pos][i],ans+b[i]);
35          break;
36      }
37      return ;
38 }
39 signed main()
40 {
41      scanf("%lld%lld%lld",&n,&k,&m);
42      for(int i=1;i<=m;++i)
43      {
44          scanf("%lld%lld%lld",&a[i],&b[i],&t[i]);
45      }
46      for(int i=1;i<=m;++i)
47      {
48          for(int j=1;j<=m;++j)
49          {
50               dis[i][j]=abs(a[i]-a[j]);
51          }
52      }
53      int l=0,r=0;
54      for(int i=1;i<=m;++i)
55      if(a[i]<=k&&abs(a[i]-k)+1<=t[i])l=i;  
56      for(int i=m;i>=1;--i)
57      if(a[i]>=k&&abs(a[i]-k)+1<=t[i])r=i;
58      if(l!=0)
59      find(l,min(a[l],k),max(a[l],k),abs(a[l]-k)+1,b[l]);
60      if(r!=0)
61      find(r,min(a[r],k),max(a[r],k),abs(a[r]-k)+1,b[r]);     
62      printf("%lld\n",sum);
63 }