1．小x的旅行
(travel.pas/c/cpp)
【问题描述】
小x大学毕业后，进入了某个公司做了高层管理，他每年的任务就是检查这个公司在全国各地N个分公司的各种状况，每个公司都要检查一遍，且只能检查一遍，也就是说这N个地方只能也必须去一次。
当然，小x每年可以选择从任意一个城市开始，任意一个城市结束。
现在给出这N个公司所在地任意两个地点飞机票的价格，现在小x为了给公司省下交通费，需要设计一个程序，来计算一下如何花费最低能够完成任务。
作为一名有过信息学竞赛经历的有志青年，小x给自己的路线又规定了一个约束条件：如果要访问编号为K的城市，那么编号比K小的所有城市或者在访问K之前访问，或者在访问K之后访问。这个条件也必须遵守。
比如：如果有3个城市：2 1 3和 3 1 2 的顺序都是合法的，但是 1 3 2的顺序就是非法的，因为比3小的1在3之前，2在3之后，和小x的要求冲突。
【输入】
第一行：一个整数N。
接下来N行，每行N个整数。第i行第j列的值a[i][j]表示第i个城市到第j个城市飞机票的价格。保证这N个整数在[0..1000]之间。
【输出】
一个整数，表示满足要求的最小花费。
【输入输出样例1】
|
travel.in |
travel.out |
|
3 0 5 2 5 0 4 2 4 0 |
7 |
【输入输出样例2】
|
travel.in |
travel.out |
|
4 0 15 7 8 15 0 16 9 7 16 0 12 8 9 12 0 |
31 |
【样例解释】顺序为3, 1, 2, 4 或者 4, 2, 1, 3.
【数据范围】
30% 数据保证N<=10
50% 数据保证 N<=20
100% 数据保证 N<=1500
思路：
第一反应是dfs，但是如何判断是否符合题意呢？（反正我不会）。
仔细想想，点1不在中间，就在对头或队尾。那我们从1枚举到n分别放在上一次l，r的两边不就行了。
代码也不长。
Here is it；
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<cstdlib> 6 #include<string> 7 #include<iomanip> 8 #include<ctime> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 const int maxn=5000001; 13 int n,a[2000][2000]; 14 int f[2000][2000]; 15 int ans=maxn; 16 17 int dfs(int l,int r) 18 { 19 if(f[l][r]) return f[l][r]; 20 int next=max(l,r)+1; 21 if(next==n+1) 22 { 23 return 0; 24 } 25 return f[l][r]=min(a[next][l]+dfs(next,r),a[r][next]+dfs(l,next)); 26 } 27 28 int main() 29 { 30 freopen("travel.in","r",stdin); 31 freopen("travel.out","w",stdout); 32 ios::sync_with_stdio(false); 33 cin>>n; 34 for(int i=1;i<=n;i++) 35 for(int j=1;j<=n;j++) 36 cin>>a[i][j]; 37 for(int i=1;i<=n;i++) 38 { 39 dfs(1,1); 40 } 41 cout<<f[1][1]<<endl; 42 return 0; 43 }