[USACO5.4]周游加拿大Canada Tour
动态规划+字符串处理
传送门(洛谷)
题目描述:
此题可以看成从最左边到最右边,再从右边走回左边。故我们可以看成两个人一个从左到右,一个从右到左,因此设此状态:f[i][j]表示左边的人到i号城市时和右边的人到j号城市时所走过的总城市数目
此外,用一个map处理字符串,为了方便判断两个城市是否有飞机相连
转移方程式:
if(a[j][k] && f[i][k]) //如果有j与k相连
f[i][j]=max(f[i][j],f[i][k]+1);
f[j][i]=f[i][j];
Code
#include<bits/stdc++.h>
#include<map>
#define ll long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define don(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int maxn=1e5+10;
const int maxm=1e3+10;
int n,v;
int f[maxm][maxm],a[maxm][maxm];
string s,s1,s2;
map <string,int> ma;
template <class t> inline void read(t &x)
{
x=0;int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
x*=f;
}
template <class t> inline void write(t x)
{
if(x<0){putchar('-');x=~x+1;}
if(x>9) write(x/10);
putchar(x%10+48);
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
void readdata()
{
read(n),read(v);
rep(i,1,n) {
cin>>s;
ma[s]=i;
}//个人认为,map在此地方起到转换作用
rep(i,1,v) {
cin>>s1>>s2;
a[ma[s1]][ma[s2]]=1;
a[ma[s2]][ma[s1]]=1;
}//城市路程初始化,两个城市相连则可以付为1
}
void work()
{
f[1][1]=1;
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++) {//i,j两个人一共走的城市数最大为n
for (int k=1;k<j;k++)
if(a[j][k] && f[i][k]) //如果有j与k相连
f[i][j]=max(f[i][j],f[i][k]+1);
f[j][i]=f[i][j];//一人走到j一人走到i顺序倒过来是相同的
}
int ans=1;
for(int i=1;i<=n;i++){
if(a[i][n]) ans=max(ans,f[i][n]);
}
printf("%d",ans);
}
int main()
{
// freopen("input.txt","r",stdin);
readdata();
work();
return 0;
}