题目描述

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

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

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

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

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

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

现在有?个正方体和?个球形的木娃娃，其中第?个正方体娃娃边长为??，第?个球形娃娃半径为??。用这些娃娃组成一个套娃，最多有几层？

数据保证所有正方体边长不相同，所有的圆半径不相同。

输入描述:

输入第一行为一个整数?(1 ≤ ? ≤ 25)，表示一共有?组测试数据。 对于每组测试数据： 第一行有两个整数?,?(1 ≤ ?,? ≤ 105)，分别表示正方体和球体的木娃娃数。 第二行有?个整数，其中第?个整数??(1 ≤ ?? ≤ 109)代表第?个正方体娃娃的边长。 第二行有?个整数，其中第?个整数??(1 ≤ ?? ≤ 109)代表第?个球形娃娃的半径。

输出描述:

输出一个正整数?，表示组成的套娃的层数。

示例1

输入

13 42 4 67 5 3 1

输出

5

说明

对于样例，套娃分别由半径为7的球形、半径为5的球形、边长为4的正方体、边长为2的正方体、半径为1 的球形的木娃娃组成，一共5层。

题解

$dp$。

可以构造出一个$DAG$，然后看最长路的长度就可以了。

#include 
          
           using namespace std;const int maxn = 8e5 + 10;int T;int n, m;long long a[maxn], b[maxn];int dp[maxn];int h[maxn];int to[maxn];int nx[maxn];int sz;int in[maxn];void add(int x, int y) {  //  cout << x << " -> " << y <
           

Q; for(int i = 1; i <= n + m; i ++) { if(in[i] == 0) { Q.push(i); dp[i] = 1; } } while(!Q.empty()) { int node = Q.front(); Q.pop(); ans = max(ans, dp[node]); for(int i = h[node]; i != -1; i = nx[i]) { dp[to[i]] = max(dp[to[i]], dp[node] + 1); in[to[i]] --; if(in[to[i]] == 0) { Q.push(to[i]); } } } printf("%d\n", ans); } return 0;}