大家好，又见面了，我是全栈君。
【问题背景】
11月16日：
今天要来到南极洲的一角来考察啦！南极的空气真的很好呢，只不过有点冷，雪什么的真是太可爱了！
这次我要在一个冰谷（应该说是山谷的地方）考察，考察点在这山谷的两边（希望不要掉下去！），可是我只能坐着直升机到达这些考察点中的一个（因为空中的气流少有平稳的时候），剩下的地方只能靠腿走过去了。不过我可以预定直升机在气流合适的时候到某个考察点来接我，真是方便呀！
哦！不过我还有很多设备。。。我可搬不动，不过放在滑溜溜的冰面上拉着还是可以的，我有一个吸热扩散器，可以在一些地形合适的地方建一座冰桥！看来我只能沿着冰桥走了。
QAQ我刚看了地图，似乎冰桥只能建立在跨越山谷的两个考察点间，而且不能交叉，而且最可恶的是，这些冰桥我只能走一次。。。。因为他们太脆弱了。。真糟糕，看来这次可能不能把全部的考察点都考察了。。不过我要让这次考察最有价值！
那就从分析考察点的价值开始吧，然后要好好想想怎么安排这次考察的顺序。
——美
【问题描述】
山谷两侧分别有一些考察点，每个考察点都有其价值，其中一些考察点间可以建立跨越山谷的冰桥，让小美能够从一个考察点到另一个考察点。
但是冰桥有它的缺点，它十分的脆弱，以至于只能走一次，而且不能交叉（假设两座冰桥分别连接了 a1 和 b1, a2 和 b2 ,当 a1 < a2 且 b1 > b2时两桥交叉）。
由于小美带着很多沉重的设备，所以她必须沿着冰桥走，请设计策略使得小美这次的考察的价值和最大。
【输入格式】
输入共 A+B+K+1 行。
第 1 行包含 3 个由空格隔开的非负的整数 A, B, K，表示山谷 A, B 两侧各有 A, B 个考察点，其中可以建立 K 座冰桥。
第 1 +(1) 至 1 +(A) 行，每行包含 1 个正整数，其中第 1 +(i) 行的正整数 p 表示 A 侧第 i 个考察点的价值为 p。
第 1+A +(1) 至 1+A +(B) 行，每行包含 1 个正整数，其中第 1+A +(i) 行的正整数 p 表示 B 侧第 i 个考察点的价值为 p。
第 1+A+B +(1) 至 1+A+B +(K) 行，每行包含 2 个正整数 u, v，表示 A 侧的第 u 个考察点与 B 侧的第 v 个考察点间可以建立冰桥。
【输出格式】
输出共 1 行。
第 1 行包含 1 个正整数，表示此次考察的最大价值和。
【样例输入】
3 2 4 2 2 3 1 2 3 2 2 1 1 2 3 1
【样例输出】
8
【数据规模与约定】
对于测试点 1 到 2，A <= 5; B <= 5
对于测试点 3，A <= 200; B <= 200; K <= 15,000
对于测试点 4 到 10，A <= 40,000; B <= 40,000; K <= 100,000
对于全部数据，保证 p <= 40,000; 保证冰桥没有重复
官方题解：
定义状态 FA[i], FB[i] 分别表示到达 A, B 侧的第 i 个点所能得到的最大价值和。
首先我们可以得知，冰桥不交叉的充分必要条件是同一侧被访问的点的编号递增。
对所有的边进行从小到大排序，按照排序后边的顺序进行转移。
排序后可以保证，对于每个点 u，其出边到达的点的编号在排序后是递增的，所以对于连接 a 和 b 的边，此时的 FA[a] 只会从小于 b 的点中转移而来，FB[b] 也只会从比 a 小的点转移过来，所以这时的 FA[a] 尝试从 FB[b] 转移是绝对合法的, FA[a] = max(FA[a], FB[b] + VA[a]) (保留先前最大值 或者 从B侧b点走到A侧a点)
代码：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #define MAXN 101000 using namespace std; struct edge{ int from,to; void read(){ scanf("%d%d",&from,&to); } }a[MAXN]; int dp1[MAXN],dp2[MAXN],v1[MAXN],v2[MAXN]; int A,B,K; bool cmp(edge x,edge y){ if(x.from==y.from) return x.to<y.to; return x.from<y.from; } int main() { scanf("%d%d%d",&A,&B,&K); for(int i=1;i<=A;i++) scanf("%d",&v1[i]); for(int i=1;i<=B;i++) scanf("%d",&v2[i]); for(int i=1;i<=K;i++) a[i].read(); sort(a+1,a+K+1,cmp); for(int i=1;i<=A;i++) dp1[i]=v1[i]; for(int i=1;i<=B;i++) dp2[i]=v2[i]; for(int i=1;i<=K;i++){ int from=a[i].from,to=a[i].to,d1=dp1[from],d2=dp2[to]; dp1[from]=max(dp1[from],d2+v1[from]); dp2[to]=max(dp2[to],d1+v2[to]); } int ans=0; for(int i=1;i<=A;i++) ans=max(ans,dp1[i]); for(int i=1;i<=B;i++) ans=max(ans,dp2[i]); printf("%d",ans); return 0; }
转载于:https://www.cnblogs.com/renjianshige/p/7653087.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108113.html原文链接：https://javaforall.net
