题号：NC14674 链接：https://ac.nowcoder.com/acm/problem/14674

来源：牛客网

题目描述

俄罗斯套娃是俄罗斯特产的木制玩具，一般由多个一样图案的空心木娃娃一个套一个组成，最多可达十多个，通常为圆柱形，底部平坦可以直立。颜色有红色，蓝色，绿色，紫色等。最普通的图案是一个穿着俄罗斯民族服装的姑娘，叫做“玛特罗什卡”，这也成为这种娃娃的通称。

彩虹岛也有自己的套娃，不过与俄罗斯套娃有所不同，其组成规则如下：

  1. 空心木娃娃只有正方体与球两种形状。

  2. 正方体娃娃与球体娃娃可以相互套，也可以相同形状之间套。

  3. 当两形状相切的时候使能够互相嵌套的，比如半径为2的球体能套在边长为4的正方体中。

  4. 所有木娃娃的厚度可以忽略不计。

现在有𝑛个正方体和𝑚个球形的木娃娃，其中第𝑖个正方体娃娃边长为𝑎𝑖，第𝑗个球形娃娃半径为𝑟𝑗。用这些娃娃组成一个套娃，最多有几层？ 数据保证所有正方体边长不相同，所有的圆半径不相同。

输入

1

3 4

2 4 6

7 5 3 1

输出

5

思路： 这道题可以采用dp思路（动态规划）。

dp[i] = max(dp[j] + 1, ....) 其中j满足第i个套娃可以套第j个套娃的所有j，且i!=j.

难点在于，这道题的复杂度要求比较高，直接O(n^2)也是被pass的。 需要求解上面的公式，要做到：

1.先算出所有的dp[j]值，再算dp[i].

2.求解max不能直接遍历求解，不然复杂度便是O(n^2).

针对第一个问题比较简单： 按照一定的规则排序，保证j在i的排序前面，然后按照排序进行计算即可。这个排序，可以按照如下的排序规则获得（其中一种）：

排序规则：如果是球体，其权重值为2*R，如果是正方体，其权重值为L。如果权重一致，正方体是大于球体（正方体恰好套球体），正方体排在球体后面。

很容易证明，这个排序，小正方体在大正方体的排序前面（显然），小球体在大球体的排序前面（显然）。正方体能够套住的所有球体，所有球体都在其排序前面（显然）。球体能够套住的正方体，所有正方体也在其排序前面（这个推一下也是显然的）

第二个问题：如何求解max值，其实可以优化，优化成： dp[i]=max(dp[j1], dp[j2]),

其中第j1个套娃的类型跟第i个套娃的类型一致，并且第j1个套娃是在排序中最接近第i个套娃的，或者说，第j1个套娃是同类型中，比第i个套娃次小的那个套娃。

其中第j2个套娃的类型跟第i个套娃的类型不一致，并且第j2个套娃是在能够被套得住的排序中最接近第i个套娃的不同类型套娃。

求最接近套娃的求法，可以在遍历算dp[i]的时候，顺便算出最接近的套娃，比如同类型的，在遍历中取上一次同一个同类型套娃值即可，因此复杂度为O(n).

需要注意的是第一个问题的，涉及到排序，排序最快是O(n*log(n)).排序不能使用类似冒泡排序等复杂度较高的排序，可以使用不稳定排序，比如堆排序，但快排（最坏是O(n^2)）可能不行。

附代码：

// dddd.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define MAX(x,y) ((x)>(y)?(x):(y))

using namespace std;
typedef struct Node{
	int type;
	long long len;
	int id;
}Node; 
Node data2[200020];
int dp[200020];

int NodeCmp(Node *x, Node *y) {
	if (x->type == y->type) {
		if (x->len > y->len) return 1;
		if (x->len < y->len) return -1;
	}
	else {
		int a = x->type == 1 ? x->len : 2 * x->len;
		int b = y->type == 1 ? y->len : 2 * y->len;
		if (a > b||a==b&&x->type==1) return 1;
		if (a < b||a==b&&y->type==1) return -1;
	}
	return 0;
}

template<class Class>
void duisort(Class*s, Class *e, int (*cmp)(Class*, Class*)) {
	// 大顶堆初始化
	int len = e - s;
	Node* duiTop = s - 1;
	for (int i = len / 2; i >= 1; i--) {
		// 下沉
		int ii = i;
		while (2 * ii <= len) {
			int j = 2 * ii;
			if (j + 1 <= len && cmp(duiTop + j + 1, duiTop + j) > 0) j++;
			if (cmp(duiTop + ii, duiTop + j) < 0) {
				Node x = duiTop[ii];
				duiTop[ii] = duiTop[j];
				duiTop[j] = x;
			}
			else break;
			ii = j;
		}
	}
	for (int i = len; i >=2; i--) {
		Node x = duiTop[i];
		duiTop[i] = duiTop[1];
		duiTop[1] = x;
		// 下沉
		int ii = 1;
		while (2 * ii <= i - 1) {
			int j = 2 * ii;
			if (j + 1 <= i-1 && cmp(duiTop + j + 1, duiTop + j) > 0) j++;
			if (cmp(duiTop + ii, duiTop + j) < 0) {
				Node x = duiTop[ii];
				duiTop[ii] = duiTop[j];
				duiTop[j] = x;
			}
			else break;
			ii = j;
		}
	}
}

int main() {
	//如果半径R和正方形L满足4 * R * R >= 3 * L * L, 球可以套正方体
	//如果半径R和正方形L满足L >= 2*R, 正方体可以套球
	int t;
	//freopen("1.txt", "r", stdin);
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			data2[i].type = 1;
			cin >> data2[i].len;
		}
		for (int i = 0; i < m; i++) {
			cin >> data2[i + n].len;
			data2[i + n].type = 2;
		}

		Node temp;
		// 进行排序
		n += m;
		duisort(data2, data2 + n, NodeCmp);
		int dpSameLastValue[3] = { 0,-1,-1 };
		int dpNoSameLastKey[3] = { 0,0,0 };
		int ret = 0;
		for (int i = 0; i < n; i++) {
			data2[i].id = i+1;
			//cout << "I: 类型:" << (data2[i].type == 1 ? "正方体" : "球体") << " " << data2[i].len << endl;
			dp[i] = dpSameLastValue[data2[i].type] + 1;
			int otherType = 3 - data2[i].type;
			while (dpNoSameLastKey[otherType] < i) {
				// 如果找到可能小于自己的非同类型
				if (data2[dpNoSameLastKey[otherType]].type == otherType) {
					// 是否可以套住
					if (data2[i].type == 1 && data2[i].len >= 2 * data2[dpNoSameLastKey[otherType]].len ||
						data2[i].type == 2 && 4 * data2[i].len * data2[i].len >= 3 * data2[dpNoSameLastKey[otherType]].len * data2[dpNoSameLastKey[otherType]].len) {
						//cout << "I: 套住 " << (i + 1) << "->" << data2[dpNoSameLastKey[otherType]].id << " max(" << dp[i] << "," << (dp[dpNoSameLastKey[otherType]] + 1) << ")" << endl;
						dp[i] = MAX(dp[i], dp[dpNoSameLastKey[otherType]] + 1);
					}
					else {
						break;
					}
				}
				dpNoSameLastKey[otherType]++;
			}
			dpSameLastValue[data2[i].type] = dp[i];
			ret = MAX(ret, dp[i] + 1);
			//cout << "I: 结果 第" << (i + 1) << " -->" << dp[i]<<endl<<endl;
		}
		cout << ret << endl;
	}
	return 0;
}