鹰蛋(北大2023年最强新生的题)

2023-12-14 22:32:33

这个牛马,在我准备上床玩手机之前发这一道题(23:00),然后我想到23:43,没想出来,就和他说明天再想,躺床上玩手机到00:30,过程中脑子里萦绕着这道题,然后准备睡觉,睡不着,一直想着怎么解题,然后准备起来写思路了,一看手机,1:00,最后写到了1:41,题解出来了,安然睡觉,第二天早八,想死

那么如何动态规划?

设行代表蛋数,列代表层数

当求dp[i][j]的时候,设第一颗蛋放在第k层,如果蛋碎了,此时的试验数是1+dp[i - 1][j - k],如果蛋没碎,此时的试验数是1+dp[i][k - 1],因为是最坏结果,所以第一颗蛋放在第k层的最坏结果Sk = max{1+dp[i - 1][j - k],1+dp[i][k - 1]}

而dp[i][j] = min{Sk}(k = 1,2,3……j}

这样就求完了

但是还是得优化

我画了一个图像:

下面的N要改成j

要求的dp[i][j]就在交点附近,而Sk是组合起来的,位于上方的线

就可以用二分法来求

代码如下:

#include<stdio.h>
#include<stdlib.h>
void dichotomy(int A, int B, int j);//j代表此时的最高层
int N, M, minn, * dp_pvs, * dp_nxt;//previous, next

int main(void)
{
    while(1)
    {
        //输入
        scanf("%d%d", &N, &M);
        if(N == 0)  break;
        //预处理
        dp_pvs = (int *)malloc(N * sizeof(int)), dp_nxt = (int *)malloc(N * sizeof(int));
        for(int i = 1; i <= N; i++)
            * (dp_pvs + i) = i;
        //开始动态规划
        for(int i = 2; i <= M; i++)
        {
            for(int j = 1; j <= i; j++)
                * (dp_nxt + j) = * (dp_pvs + j);
            for(int j = i + 1; j <= N; j++)
            {
                //二分法求最优值
                int tmp1 = * (dp_nxt + (j - i)) + 1, tmp2 = * (dp_pvs + j - 1) + 1;
                minn = (tmp1 < tmp2) ? tmp1 : tmp2;
                if(j - i > 1)  dichotomy(i, j, j);
                * (dp_nxt + j) = minn;
            }
            //一层求完,交换指针
            int * tmp = dp_pvs;
            dp_pvs = dp_nxt;
            dp_nxt = tmp;
        }
        //输出
        printf("%d\n", * (dp_pvs + N));
        free(dp_nxt), free(dp_pvs);
    }

    return 0;
}
void dichotomy(int A, int B, int j)
{
    int k = (A + B) / 2;
    int tmp1 = * (dp_pvs + k - 1) + 1, tmp2 = * (dp_nxt + (j - k)) + 1;//碎了和没碎
    int maxn = (tmp1 > tmp2) ? tmp1 : tmp2;
    minn = (minn < maxn) ? minn : maxn;

    if(tmp1 > tmp2 && k - A > 1)  dichotomy(A, k, j);
    else if(tmp1 < tmp2 && B - k > 1)  dichotomy(k, B, j);
    return;
}

超时了

改了一下,用了链表,对于多组数据可以一次算完

代码如下:

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
	ElemType n;
    ElemType m;
    ElemType id;
	struct LNode * next;
}LinkList;
LinkList * creat(int n);
void DestroyList(LinkList * head);
void dichotomy(int A, int B, int j);//j代表此时的最高层
int N, M, minn, count = 1, * result, * dp_pvs, * dp_nxt;//previous, next

int main(void)
{
    //输入
    LinkList * head = creat(1);
    head->next->id = 0;
    while(1)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        if(!n) break;
        N = (N > n) ? N : n, M = (M > m) ? M : m;
        //插入排序
        for(LinkList * node = head->next, * f_node = head; 1; node = node->next, f_node = f_node->next)
        {
            if(node == NULL || m < node->m || (m == node->m && n < node->n))
            {
                LinkList * tmp = (LinkList *)malloc(sizeof(LinkList));
                f_node->next = tmp, tmp->next = node;
                tmp->m = m, tmp->n = n, tmp->id = count;
                break;
            }
        }
        count++;
    }
    result = (int *)malloc(count * sizeof(int));;
    //预处理
    dp_pvs = (int *)malloc(N * sizeof(int)), dp_nxt = (int *)malloc(N * sizeof(int));
    LinkList * node = head->next;
    for(int i = 1; i <= N; i++)
    {
        * (dp_pvs + i) = i;
        if(node->m == 1 && node->n == i)
        {
            * (result + node->id) = i;
            node = node->next;
        }
    }
    //开始动态规划
    for(int i = 2; i <= M; i++)
    {
        for(int j = 1; j <= i; j++)
            * (dp_nxt + j) = * (dp_pvs + j);
        for(int j = i + 1; j <= N; j++)
        {
            //二分法求最优值
            int tmp1 = * (dp_nxt + (j - i)) + 1, tmp2 = * (dp_pvs + j - 1) + 1;
            minn = (tmp1 < tmp2) ? tmp1 : tmp2;
            dichotomy(i, j, j);
            * (dp_nxt + j) = minn;
            //判断并放入result
            if(node->m == i && node->n == j)
            {
                * (result + (node->id)) = minn;
                node = node->next;
                if(node == NULL)  break;
            }
        }
        //一层求完,交换指针
        int * tmp = dp_pvs;
        dp_pvs = dp_nxt;
        dp_nxt = tmp;
    }
    //输出
    for(int i = 0; i < count; i++)
        printf("%d\n", * (result + i));
    DestroyList(head);

    return 0;
}
LinkList * creat(int n)
{
	LinkList * head, * node, * end;//定义头节点,普通节点,尾部节点
	head = (LinkList *)malloc(sizeof(LinkList));//分配地址
	end = head;
	for(int i = 0; i < n; i++)
	{
		node = (LinkList *)malloc(sizeof(LinkList));//分配地址
		scanf("%d%d", &node->n, &node->m);
        N = (N > node->n) ? N : node->n, M = (M > node->m) ? M : node->m;
		end->next = node;
		end = node;
	}
	end->next = NULL;//结束创建
	return head;
}//创建长度为n的链表
void DestroyList(LinkList * head)
{
	LinkList * end = head;
	do
	{
		end = end->next;
		free(head);
		head = end;
	}while(end != NULL);
	return;
}//销毁链表
void dichotomy(int A, int B, int j)
{
    if(B - A <= 1) return;
    int k = (A + B) / 2;
    int tmp1 = * (dp_pvs + k - 1) + 1, tmp2 = * (dp_nxt + (j - k)) + 1;//碎了和没碎
    int maxn = (tmp1 > tmp2) ? tmp1 : tmp2;
    minn = (minn < maxn) ? minn : maxn;

    if(tmp1 > tmp2)  dichotomy(A, k, j);
    else if(tmp1 < tmp2)  dichotomy(k, B, j);
    return;
}

如果还是超时就是我太菜了

多学学算法吧

文章来源:https://blog.csdn.net/Fool256353/article/details/135001375
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。