这是一道典型的dp题。ZC的解题报告告诉我.......

自己看吧。辛辛苦苦写了15分钟的我的解题报告被Maxthon的鼠标手势给毁了，我真倒霉。

我的算法更加保险，也可以理解为更加笨拙。有一点不明白的地方是为什么他可以用该杀的贪心？这怎么可以用贪心？呜......我就等于O(n^4)了。

#include <cstdio>
#include <string>
int n, an, bn, a[101], b[101], r[101][101];

void dp()
{
 int i, k, mx, j, u;
 memset(r, 0, sizeof(r));
 for(i = 1; i <= an; i ++)
 {
  for(k = 1; k <= bn; k ++)
  {
   mx = 0;
   if(a[i] != b[k])
   {
    for(j = i - 1; j > 0; j --)
    {
     if(a[j] == b[k])
     {
      for(u = k - 1; u > 0; u --)
      {
       if(b[u] == a[i])
       {
        if(u && j && mx < r[j - 1][u - 1] + 2)
        {
         mx = r[j - 1][u - 1] + 2;
        }
       }
      }
     }
    }    
   }
   if(mx < r[i - 1][k])
    mx = r[i - 1][k];
   if(mx < r[i][k - 1])
    mx = r[i][k - 1];
   if(mx < r[i - 1][k - 1])
    mx = r[i - 1][k - 1];
   r[i][k] = mx;
  }
 }
}

void print()
{
 //pr();
 printf("%d\n", r[an][bn]);
}

int main()
{
 //freopen("in.txt", "r", stdin);
 scanf("%d", &n);
 int i, k;
 for(i = 0; i < n; i ++)
 {
  scanf("%d %d", &an, &bn);
  for(k = 1; k <= an; k ++)
  {
   scanf("%d", &a[k]);
  }
  for(k = 1; k <= bn; k ++)
  {
   scanf("%d", &b[k]);
  }
  dp();
  print();
 }
 return 0;
}
  

评论