首页 > 代码库 > zoj1425解题报告

zoj1425解题报告

   刚开始题目意思理解错了,以为一个匹配允许被多个匹配交叉,然后取一个匹配满足条件即可。于是错了.

   如:1 3 2 4

       2 4 1 3 的答案应该是2而不是4.一个匹配只能允许被有且只有一个匹配交叉.   

  那么我们从起点开始上段起点为i,下段起点为j,判断i,j是否能构成满足条件的匹配.若i1,j1构成满足条件使ij1,ji1交叉并不相等则maxs = max{maxs,2+dp[i1+1][j1+1]}

若不满足则maxs = max{maxs,dp[i+1][j+1]||dp[i][j+1]||dp[i+1][j]};

  代码如下:

  #include <set>
  #include <map>
  #include <queue>
  #include <stack>
  #include <math.h>
  #include <string>
  #include <vector>
  #include <stdio.h>
  #include <stdlib.h>
  #include <iostream>
  #include <limits.h>
  #include <string.h>
  #include <algorithm>
  #include <functional>
  using namespace std;
  int start[105];//上端的数据
  int ended[105];//下端的数据
  int dp[105][105];//dp[i][j],从i,j开始能得到最大匹配.
  int m,n;
  int dfs(int i,int j){
     if(i >= m-1 || j >= n-1) return 0;
     if(dp[i][j] >= 0) return dp[i][j];
     int maxs = 0;
     for(int x = j + 1;x < n;x++){
       /*是否i与i1相等*/ if(ended[x] == start[i]){ 
             for(int y = i + 1;y < m;y++){
         /*是否j与j1相等,并且i与j的匹配不相等*/ if(ended[j] != start[i] && start[y] == ended[j]){
                     maxs = max(maxs,2+dfs(y+1,x+1));
                 }
             }
          }
      }
      maxs = max(maxs,dfs(i+1,j));
      maxs = max(maxs,dfs(i,j+1));
      maxs = max(maxs,dfs(i+1,j+1));
      return dp[i][j] = maxs;
   }
   int main(){
   int t;
   scanf("%d",&t);
   int i,j;
   while(t--){
    scanf("%d%d",&m,&n);
    for(i = 0;i < m;i++)
    scanf("%d",&start[i]);
    for(i = 0;i < n;i++)
    scanf("%d",&ended[i]);
    memset(dp,-1,sizeof(dp));
    dfs(0,0);
    printf("%d\n",dp[0][0]);
}
return 0;
}

zoj1425解题报告