题解 P2747 【[USACO5.4]周游加拿大Canada Tour】

远航之曲 · 2016-11-01 15:54:37 · 题解

一道基础的dp

把返回的路线反向，那么整条路线就变成了两条不相交的从起点到终点的路线。这样我们可以用DP解决。

状态设定

f[i,j] 为假定的甲乙两人，甲走到第i个城市，乙走到第j个城市时，两人走过的城市数目的和。

初始状态

f[1,1]=1

状态转移方程

f[j,i]=f[i,j]=max{f[i,k]+1}(k到j存在飞机航线，以及f[i,k]>0，就是说存在f[i,k]的走法，1<=k<j，i<j<=n

交换甲乙，则肯定有f[j,i]=f[i,j]。

目标结果

由于题中告知必须走到终点才能返回，输出结果一定是max{f[i,N]}(i到N存在飞机航线)。 如果没有经过城市数目大于1的可行目标状态，则无法完成这次环游，输出1。

#include <cstdio>
#include <string>
#include <map>
#include <iostream>
#include <cstring>
using namespace std;
string s,s1,s2;
int n,m,f[110][110],a[110][110];
map <string,int> ma;
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        ma[s]=i;
    }
    for (int i=1;i<=m;i++)
    {
        cin>>s1>>s2;
        a[ma[s1]][ma[s2]]=1;
        a[ma[s2]][ma[s1]]=1;
        //printf("%d %d\n",ma[s1],ma[s2]);
    }
    //memset(f,-1,sizeof f);
    f[1][1]=1;
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
        {
            for (int k=1;k<j;k++)
                if (a[j][k]&&f[i][k]) 
                    f[i][j]=max(f[i][j],f[i][k]+1);
            f[j][i]=f[i][j];
        }
    int ans=1;
    for (int i=1;i<=n;i++)
        if(a[i][n])
            ans=max(ans,f[i][n]);
    printf("%d",ans);
}