2035433 2006-08-21 15:25:00 Accepted 1425 C++ 00:00.01 432K St.Crux 这是一道典型的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;}  

评论