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 1007

string 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;
}