首页 > 代码库 > 2014 Super Training #2 F The Bridges of Kolsberg --DP
2014 Super Training #2 F The Bridges of Kolsberg --DP
原题：UVA 1172 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3613
动态规划问题。
定义： 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 <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>using namespace std;#define N 1007string os1[N],os2[N];int osind1[N],osind2[N];int cost1[N],cost2[N];pair<int,int> dp[N];map<string,int> 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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。