poj1682

题目大意:在三个河岸X,Y,Z上分别有n,m,k个部落,要求用最少的费用,使每个部落都能通过至少一座桥与其它河岸联系.

期中桥梁不能交叉.每条桥梁需要的费用为两个部落海拔差的绝对值.

思路：两两进行dp。。然后枚举交点在进行dp一次。。

即多重dp

 1 /*
 2   State:Accepted
 3   Time:2013-03-08 20:49:50
 4 */
 5 #include <iostream>
 6 #include <fstream>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <algorithm>
10 #include <cmath>
11 #include <cstring>
12 #define MXN  105
13 using namespace std;
14 int a[MXN],b[MXN],f[MXN][MXN] , n , m ,p ,ans , T ;
15 
16 int max(int x , int y){ 
17     return x > y? x : y;
18 };
19 
20 void init(){
21       scanf("%d%d",&n, &m);
22       for (int i = 1; i <= n; ++i)  
23           scanf("%d" , &a[i]);   
24       for (int i = 1; i <= m; ++i)  
25           scanf("%d" , &b[i]);   
26 }
27 
28 void dp(){
29       memset(f , 0 ,sizeof(f));
30       for (int i = 2; i <= n; ++i)
31          for (int j = 2; j <= m; ++j){
32              f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
33              f[i][j] = max(f[i][j] , f[i - 1][j -1]);
34              if (a[i]!=b[j]){
35                    int k1 , k2;
36                    for (k1 = i - 1; k1 > 0 ; --k1)
37                        if (a[k1] == b[j]) break;
38                    for (k2 = j - 1; k2 > 0; --k2)
39                        if (a[i] == b[k2]) break;
40                        
41                    if (k1&&k2) f[i][j] = max(f[i][j] , f[k1 - 1][k2 - 1] + 2);
42                      
43             }
44          }
45 
46       printf("%d\n",f[n][m]);
47 }
48 
49 int main(){
50       freopen("poj1692.in","r",stdin);
51       freopen("poj1692.out","w",stdout);
52       scanf("%d",&T);
53       for (int i = 1; i <= T; ++i){
54           init();
55           dp();
56       }
57       fclose(stdin); fclose(stdout);
58 }