套娃(dolls)
问题描述：
套娃游戏大家一定玩过，套娃在嵌套放入的时候，每一个套娃只可以嵌入高．
度和长度均比它大
．．．．．．．．的套娃内。现在有一批套娃，给出它们的高度和长度，计算最
少能嵌套出几组套娃。
输入格式：
第一行为正整数t(≤5)，表示数据组数；每组数据中，第一行为正整数m(≤
30000)，表示一共有m只套娃；接下来m行，每行两个正整数wi和hi(wi,hi≤10
5)，
分别表示每一只套娃的高度和长度。
输出格式：
对于每组数据，输出最少嵌套的组数。
输入样例2
4
2030
1010
3020
4050
3
1030
2020
3010
2
输出样例

运行结果：

代码：

#include <iostream>
using namespace std;
 
typedef struct _toys
{
    int w;
    int h;
}MyToy;
 
typedef struct _linknode
{
    MyToy data;
    _linknode* next;
}LinkNode,*List;
 
 
//释放内存
void release(List head)
{
    while (head)
    {
        List q = head->next;
        delete head;
        head = q;
    }
}
 
//判断test是否能插入head
List Judege(List head, List test)
{
    List p = head;
    while (p->next)
    {
        if (test->data.w < p->next->data.w && test->data.h < p->next->data.h) //再前面插入
        {
            return p;
        }
        else if (test->data.w > p->next->data.w && test->data.h > p->next->data.h)
            p = p->next;
        else
            return 0;
    }
    return p;
}
 
 
void Deal(List head)
{
    List p = head;
    List allLinks[30001] = { 0 };
    int kk = 0;
    if (head->next == 0)
        cout << "0" << endl;
 
    while (head->next)
    {
        //将第一个节点从队列中取出
        List q = head->next; 
        head->next = q->next;
        //插入新的队列
        q->next = 0;
        allLinks[kk] = new LinkNode;
        allLinks[kk]->next = q;
        
 
        //从链表中查找能嵌套该娃娃的其它娃娃
        List scHead = head;
        while (scHead->next)
        {
            //判断scHead->next指向的娃娃能否嵌套该娃娃
            List pre = Judege(allLinks[kk], scHead->next);
            if (pre)//可以插入,pre是可以插入的节点的前一个节点
            {
                //将scHead->next从原链表中删除
                List tmp = scHead->next;
                scHead->next = tmp->next;
                //将scHead->next插入新链表
                tmp->next = pre->next;
                pre->next = tmp;
            }
            else
            {
                scHead = scHead->next;
            }
        }
        kk++;
    }
 
    cout << kk << endl;
    for (int x = 0; x < kk; x++)
    {
        release(allLinks[x]);
        allLinks[x] = 0;
    }
    delete head;
    head = 0;
}
 
 
 
int main()
{
    int T;
    int n;
    
    cin >> T; //测试数据组数
    for (int i = 0; i < T; i++)
    {
        //输入数据
        cin >> n;
        List all = new LinkNode;
        all->next = 0;
        List pt = all;
        for (int j = 0; j < n; j++)
        {
            List np = new LinkNode;
            cin >> np->data.w >> np->data.h;
            np->next = 0;
            pt->next = np;
            pt = np;
        }
                
        //处理
        Deal(all);
        
    }
    return 0;
}
 
 

【以下回答由 GPT 生成】

解决方案

我们可以使用动态规划的方法解决这个问题。

首先，我们将套娃按照高度从低到高进行排序。

然后，我们用一个数组dp来记录每个套娃能够嵌套的最大组数。

对于dp数组的初始化，我们将每个元素初始化为1，表示每个套娃至少可以嵌套成一组。

接下来，我们遍历每个套娃，对于每个套娃i，我们遍历所有套娃j (0 <= j < i)，如果套娃i的高度和长度都大于套娃j的高度和长度，说明套娃i可以嵌套在套娃j中，此时我们更新dp[i]的值为dp[j] + 1。

最后，我们返回dp数组中的最大值，即为最少嵌套的组数。

下面是用Python编写的实现代码：

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632