洛谷P2747周游加拿大Canada Tour [USACO5.4] dp

时间：2023-02-04 04:16:56

正解:dp

解题报告:

传送门!

其实这题是我做网络流的时候发现了这题,感觉有点像双倍经验,,,?

但是我还不想写网络流的题解,,,因为网络流24题都还麻油做完,,,想着全做完了再写个总的题解什么的(主要是不想写题解了,,,能拖几天拖几天趴QAQ

但是这题还能用dp做昂,所以我还是先写个dp的题解趴,关于网络流的做法我之后应该也会写的QAQ

首先考虑到,它说什么,从1到n再回到1,不能经过相同的城市

这就很难想昂,,,感觉很复杂的样子

所以变成从1到n走两次,不经过相同的城市

这样子就和传纸条那题差不多了,只是那个是二维这个是一维

就设f[i][j],一个到i一个到j,可以强制j>i,转移起来就是枚k∈[1,j),f[i][j]={f[i][k]+1}min

ans就是{f[i][n]}min,只是记得判一下必须i和n是直接相邻的QAQ

然后就over了

然后说下双倍经验是网络流24题中的这题,我就不放代码了实在差不多QAQ

overr!

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define ll long long

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge[i].fy

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt)

const int N=+;

int n,m,link[N][N],f[N][N],as=;

map<string,int>nam;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

int main()

{

    n=read();m=read();memset(f,-,sizeof(f));f[][]=;

    rp(i,,n){string str;cin>>str;nam[str]=i;}

    rp(i,,m){string str1,str2;cin>>str1>>str2;link[nam[str1]][nam[str2]]=link[nam[str2]][nam[str1]]=;}

    rp(i,,n)

        rp(j,i+,n)

            rp(k,,j-)if(link[k][j])f[i][j]=f[j][i]=max(f[i][k]+,f[i][j]);

    rp(i,,n)if(link[i][n])as=max(as,f[i][n]);printf("%d\n",as);

    return ;

}

放下代码QAQ

相关文章