洛谷P2747周游加拿大Canada Tour [USACO5.4] dp
正解: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=100+20;
int n,m,link[N][N],f[N][N],as=1;
map<string,int>nam;
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
int main()
{
n=read();m=read();memset(f,-63,sizeof(f));f[1][1]=1;
rp(i,1,n){string str;cin>>str;nam[str]=i;}
rp(i,1,m){string str1,str2;cin>>str1>>str2;link[nam[str1]][nam[str2]]=link[nam[str2]][nam[str1]]=1;}
rp(i,1,n)
rp(j,i+1,n)
rp(k,1,j-1)if(link[k][j])f[i][j]=f[j][i]=max(f[i][k]+1,f[i][j]);
rp(i,1,n)if(link[i][n])as=max(as,f[i][n]);printf("%d\n",as);
return 0;
}