XMOJ3065 旅游线路

10分钟没啥思路就去看题解了，结果发现很蠢。

题目大意

有一条河，河的东侧和西侧分别有 $n,m$ 个景点，每个景点有个权值。有 $k$ 条船，每条船连接东侧和西侧的一个景点。定义一个旅游线路是通过船连接起来的景点序列。一个旅游线路合法当且仅当线路中任意两条船不相交，即不存在两条船 $(x_1,y_1)$， $(x_2,y_2)$使得 $x_1＞x_2$ 并且 $y_1＜y_2$ ，或者 $x_1=x_2,y_1=y_2$。一个旅游线路的权值定义为线路中所有景点权值之和，求美丽值最大的合法旅游线路。

$n,m\le 40000$，$k\le 10^5$。

题解

发现一条合法线路当且仅当下一个东侧点大于上一个东侧点，下一个西侧点大于上一个西侧点，也就是“z”形走位。

于是将每条边排序，东侧点为第一关键字，西侧点为第二关键字，这样可以保证每次选的边都和前面不相交。因为对于走到某个东侧点时，西侧点比他小的总是先被选完，而对于一个西侧点也同理。

然后就可以直接dp了。

感觉这个排序很神奇，明明思路很直接但就是一下子没想到。太聪明了。

Code

#include<bits/stdc++.h>
using namespace std;

const int N=40000+5,M=1e5+5,INF=1e9;

int n,m,k,ans,a[N],b[N],f[N][2];

struct giao{
int a,b;
}c[M];

bool cmp(giao x,giao y){
return x.a!=y.a?x.a<y.a:x.b<y.b; 
}

int main(){
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][0]=a[i];
ans=max(ans,a[i]);
}
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
f[i][1]=b[i];
ans=max(ans,b[i]);
}
for(int i=1;i<=k;i++)
scanf("%d%d",&c[i].a,&c[i].b);
sort(c+1,c+1+k,cmp);
for(int i=1;i<=k;i++){
int sa=f[c[i].b][1]+a[c[i].a],sb=f[c[i].a][0]+b[c[i].b];
f[c[i].a][0]=max(f[c[i].a][0],sa);
f[c[i].b][1]=max(f[c[i].b][1],sb);
ans=max(ans,max(f[c[i].a][0],f[c[i].b][1]));
}
printf("%d",ans);
return 0;
}

原文地址：https://blog.csdn.net/m0_53714683/article/details/142330207

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！