UVA 10635 王子和公主

【题目描述】：王子和公主

一个王子和公主在n*n的格子中行走，这些格子是有1....n^2的编号的。现在给定p+1个数，再给定q+1个数，公主和王子可以选择其中某些格子行走，求他们最多能走几个相同的格子。

【算法分析】：

这道题读题是关键，然后我们发现需要的是公共的格子，又需要是这个步数最大化，可以想到最长公共子序列的模型。序列长度小于等于62500，最长公共子序列复杂度是n^2，超时，书上提供了把公共子序列退化到最长上升子序列的方法。以第一个系列为参照，编号1.....p+1,因为格子的数字是不重复的，且最大编号是62500，空间上满足。给第二个序列重新标号，求最长上升子序列就可以了。代码中的LIS方法是nlg2(n)的。

【总结】：首先要知道这个退化模型的局限性：1、数字不重复；2、标号小于等于62500（数字较小可存储）。

解决第一个问题：

举例： 7 4 1 1 6 7 3

1 2 1 7 4 2 7

理想标号： 1 2 3 4 5 6 7

3 0 4 1 2 0 6

我们对每一个重复的数字，例如1，在1这个节点上用MAP<int,vector>,把3,4的序列用vector按顺序存储即可，读数的时候，按照从小到大的顺序标号即可。因为标号本身是从小到大的，所以保证解的最大化。那么到这里，我们统一用map存储好了，出现一次的数字，在vector中只有一个元素。

解决第二个问题：

把大数统一用哈希表存储就可以了，同样能满足编号不重复。

【完整代码】：

  1 #include<iostream>
  2 
  3 #include<stdio.h>
  4 
  5 #include<string.h>
  6 
  7 #include<algorithm>
  8 
  9 #include<stdlib.h>
 10 
 11 #include<math.h>
 12 
 13 #include<queue>
 14 
 15 #include<vector>
 16 
 17 #include<map>
 18 
 19 #define MAXN 62500+10
 20 
 21 #define MAXM 20000+5
 22 
 23 #define oo 9556531
 24 
 25 #define eps 0.000001
 26 
 27 #define PI acos(-1.0)//这个精确度高一些
 28 
 29 #define REP1(i,n) for(int i=0;i<(n);i++)
 30 
 31 #define REP2(i,n) for(int i=1;i<=(n);i++)
 32 
 33 using namespace std;
 34 
 35  
 36 
 37 int A[MAXN];
 38 
 39 int B[MAXN];
 40 
 41 int C[MAXN];//存储转化位置信息
 42 
 43 int n,p,q,cas=0;
 44 
 45 int cnt;
 46 
 47 void builtC()
 48 
 49 {
 50 
 51     cnt=0;
 52 
 53     for(int i=0;i<MAXN;i++) C[i]=0;
 54 
 55     for(int i=0;i<p+1;i++) C[A[i]]=i+1;
 56 
 57     for(int i=0;i<q+1;i++) if (C[B[i]]!=0) A[cnt++]=C[B[i]];
 58 
 59 }
 60 
 61 int d[MAXN],g[MAXN];
 62 
 63 int LIS(int a[], int n)
 64 
 65 {
 66 
 67     int i, j, * b = new int[n + 1], ans = 0;
 68 
 69     b[ans] = - 0x3f3f3f3f;
 70 
 71     for(i = 0; i < n; i ++)
 72 
 73     {
 74 
 75         j = upper_bound(b, b + ans + 1, a[i]) - b;
 76 
 77         if(j > ans)
 78 
 79             b[++ans] = a[i];
 80 
 81         else if(a[i] < b[j])
 82 
 83             b[j] = a[i];
 84 
 85     }
 86 
 87     delete b;
 88 
 89     return ans;
 90 
 91 }
 92 
 93 //}
 94 
 95 int main()
 96 
 97 {
 98 
 99     cin>>cas;
100 
101     for(int k=1;k<=cas;k++)
102 
103     {
104 
105         cin>>n>>p>>q;
106 
107         for(int i=0;i<p+1;i++) cin>>A[i];
108 
109         for(int i=0;i<q+1;i++) cin>>B[i];
110 
111         builtC();
112 
113         cout<<"Case "<<k<<": "<<LIS(A,cnt)<<endl;
114 
115     }
116 
117     return 0;
118 
119 }

【关键词】：最长上升子序列、最长公共子序列的转化