本文共 1623 字，大约阅读时间需要 5 分钟。
原题：UVA 1172
动态规划问题。
定义： dp[i] = 右岸前i个村庄(m岸)能够与左岸(n岸)不交叉匹配的最大权值和最小桥数 （用pair<int,int> 维护两个值）
方程：
dp[i].first = max(dp[i].first,dp[i-1].first（i>=1）+cost1[i]+cost2[j]) when 左岸的i与右岸的j相匹配
dp[i].second = dp[i-1].second（i>=1）+1 (if 上面dp[i].first更小)
从后往前枚举，然后从前往后更新。
代码：
#include #include #include #include #include #include #include #include using namespace std;#define N 1007string os1[N],os2[N];int osind1[N],osind2[N];int cost1[N],cost2[N];pair dp[N];map mp;int main(){ int t,i,j,n,m; int now; string tmp; scanf("%d",&t); while(t--) { now = 1; mp.clear(); scanf("%d",&n); for(i=1;i<=n;i++) { cin>>tmp>>os1[i]>>cost1[i]; if(!mp[os1[i]]) mp[os1[i]] = now++; osind1[i] = mp[os1[i]]; } scanf("%d",&m); for(i=1;i<=m;i++) { cin>>tmp>>os2[i]>>cost2[i]; if(!mp[os2[i]]) mp[os2[i]] = now++; osind2[i] = mp[os2[i]]; } int maxi = max(n,m); for(i=0;i<=maxi;i++) dp[i] = make_pair(0,0); for(i=1;i<=n;i++) { for(j=m;j>=1;j--) { if(osind1[i] != osind2[j]) continue; int k,num; if(j >= 2) { k = dp[j-1].first + cost1[i] + cost2[j]; num = dp[j-1].second + 1; } else { k = cost1[i] + cost2[j]; num = 1; } if(dp[j].first < k) { dp[j].first = k; dp[j].second = num; } else if(dp[j].first == k) dp[j].second = min(dp[j].second,num); } for(j=2;j<=m;j++) { if(dp[j].first < dp[j-1].first) dp[j] = dp[j-1]; else if(dp[j].first == dp[j-1].first && dp[j].second > dp[j-1].second) dp[j] = dp[j-1]; } } printf("%d %d\n",dp[m].first,dp[m].second); } return 0;}
转载于:https://www.cnblogs.com/whatbeg/p/3814966.html
