Prince and princess——需要优化的DP

一个时间效率为o（nlogn）的算法求公共子序列的应用

Prince and princess

题目大意（已翻译）

在nxn的棋盘上，王子和公主玩游戏。棋盘上的正方形编号为1、2、3 ... n * n，如下所示：
Prince站在正方形1中，进行p跳跃，最后到达正方形n * n。他最多只能进入一个广场。因此，如果我们使用xp表示他输入的第p个平方，则x1，x2，... xp + 1都不同。注意，x1 = 1，xp + 1 = n * n。公主做类似的事情-站在方格1中，使q跳，最后到达方格n * n。我们使用y1，y2，... yq + 1表示序列，并且所有q + 1数均不同。
下面的图2显示了一个3x3的正方形，这是Prince的可能路线，而Princess的路线则不同。
王子按照以下顺序移动：1-> 7-> 5-> 4-> 8-> 3-> 9（黑色箭头），而公主按照以下顺序移动：1-> 4 -> 3-> 5-> 6-> 2-> 8-> 9（白色箭头）。
国王-他们的父亲刚来。“为什么要分开走？你是兄弟姐妹！” 国王说：“忽略一些跳跃，确保你们一直在一起。”
例如，如果王子忽略了他的第二，第三，第六跳，他将遵循以下路线：1-> 4-> 8->9。如果公主忽略了她的第三，第四，第五，第六跳，她将遵循相同的路线：1-> 4-> 8-> 9（常见路线如图3所示），因此满足了国王（如上所示）。国王想知道他们可以一起走的最长路线，你能告诉他吗？
输入值
输入的第一行包含一个整数t（1 <= t <= 10），后面是测试用例的数量。对于每种情况，第一行包含三个整数n，p，q（2 <= n <= 250，1 <= p，q <n * n）。第二行包含p + 1个不同的整数，范围为[1..n * n]，即Prince的序列。第三行包含q + 1个不同的整数，范围为[1..n * n]（公主的序列）。

输出量
对于每个测试案例，请打印案例编号和最长路径的长度。查看输出以获取样本输入以获取详细信息。

样本输入

1

3 6 7

1 7 5 4 8 3 9

1 4 3 5 6 2 8 9

样品输入输出

Case 1：4

一句话题意：

　　就是求最长公共子序列（这一句话能编出来这么长的故事整够可以的），直接上板子，显然，过不了￣□￣｜｜，关键点就在这个250*250上，这么大的数，你用原来那个效率那么低的算法肯定TLE啊，所以就必须得用时间效率为（nlogn）的算法

算法思路：

　　要想压缩时间效率，关键就在for循环上，做到尽可能少的遍历即可

　　1）首先我们给第一个序列的值进行按顺序的编号，即将a数组{1 7 5 4 8 3 9}变为{1 2 3 4 5 6 7}，并开一个数组将修改的值标记

　　2）对另一个序列，进行同样的编号，即根据开的标记数组赋值（同一个编号对应的值相同，若b数组中含有a中没有的值，就编号为0,因为后续操作无须考虑）

　　3）这时，公共子序列就是b中编号上升的序列，为什么？因为你进行编号就是为了便于判断顺序，肯定是要编号小的在前才能形成公共子序列，即顺序和a中一致

　　4）最后一步，二分查找b中最大上升子序列，用lowbit，效率更高

话不多说，上代码：

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn = *+,INF = 0x3f3f3f3f;

 int dp[maxn],a[maxn],b[maxn],mark[maxn];

 int main(){

     int T;scanf("%d",&T);

     int k = ;

     while(T--){

         int n,p,q;

         scanf("%d%d%d",&n,&p,&q);

         memset(mark,,sizeof(mark));

         for(int i=;i<=p+;i++){

             scanf("%d",&a[i]);

             mark[a[i]]=i; //mark数组，用于标记编号

         }

         for(int i=;i<=q+;i++){

             int x;scanf("%d",&x);

             b[i]=mark[x];  //将b数组的值也用编号存储

             dp[i]=INF;

         }

         int ans = ;，

         for(int i=;i<=q+;i++){ //动态规划部分

             int find=lower_bound(dp+,dp++i,b[i])-dp; //二分查找，这里的操作也是个关键点，可以理解为，因为已经通过编号处理数组值，所以返回的就是比他小的值个数，也就等同以b[i]为结尾的公共子序列的长度

             dp[find]=b[i];

             ans=max(ans,find);

         }

         printf("Case %d: %d\n",k,ans); //这个输出是真的恶心

         k++;

     }

     return ;

 }

我相信你理解的差不多了，反正这锅我不背(*╹▽╹*)

巴特西

Prince and princess——需要优化的DP

最新文章

热门文章