本文共 1710 字，大约阅读时间需要 5 分钟。
带有贪心思想的搜索，
我们很容易想到，对于自身来说，如果L---R区间已经走过，那么在最优策略下不会重复走
同时，每次我们都会找离本节点最近的点&&符合条件移动，
（假设我们当前不走，那么我们走到其他点才返回一定不优）
那么我们搜索的时间复杂度最大为2^100,又因为剪枝(L,R距离剪枝)，是能水掉的啦啦啦...
当然用DP做也行，我考试为啥要打状压？？？？？？？？？？？？
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define MAXN 610112 #define int long long13 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 }
转载于:https://www.cnblogs.com/Wwb123/p/11342655.html
