随笔-141  评论-9  文章-3  trackbacks-0

可以看成甲乙两个人同时从A点出发,经过不同的路径,到达B点的最长路径和。

设f[i,j]为甲走到第i座城市,乙走到第j座城市,路径的总和。

初始状态:f[1][1]=1;

转移方程:f[j, i ] = f[i,j] = max{f[i,k]+1} j,k间有路,1<=k<j

结果:ans = max{f[i,n]} i,n之有路

/*
ID: lorelei
TASK: tour
LANG: C++
*/


#include 
<fstream>
#include 
<string>

using namespace std;

const int MAX = 105;
const int INF = 0x7FFFFFF;

ifstream fin(
"tour.in");
ofstream fout(
"tour.out");

string city[105];
bool adj[MAX][MAX];
int n,v,ans;

inline 
int find(string str){
    
for(int i=1; i<=n; ++i)
        
if(str==city[i])
            
return i;
}


void input(){
    
int i;
    fin
>>n>>v;
    
for(i=1; i<=n; ++i)
        fin
>>city[i];

    
string s,t;
    
for(i=1; i<=v; ++i){
        fin
>>s>>t;
        
int v1 = find(s);
        
int v2 = find(t);
        adj[v1][v2]
=adj[v2][v1]=true;
    }

}


int f[MAX][MAX];
void solve(){
    f[
1][1]=1;
    
for(int i=1; i<=n; ++i)
        
for(int j=i+1; j<=n; ++j){
            f[i][j]
=-INF;
            
for(int k=1; k<j; ++k){
                
if(adj[k][j] && f[i][k]>0 && f[i][k]>f[i][j])
                    f[i][j]
=f[i][k];
            }

            f[j][i]
= ++f[i][j];
        }

}


void output(){
    ans
=1;
    
for(int i=1; i<n; ++i)
        
if(adj[i][n] && f[i][n]>ans)
            ans
=f[i][n];
    fout
<<ans<<endl;
}


int main(){

    input();

    solve();

    output();

    
return 0;
}



 

posted on 2011-02-14 22:49 小阮 阅读(566) 评论(1)  编辑 收藏 引用 所属分类: USACO

评论:
# re: USACO 5.4.2 Canada Tour (DP) 2012-05-02 21:45 | zyz913614263
不明白如何去除重复的,就是怎么解决两个人交叉问题?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理