洛谷 P1095 NOIP2007普及组 守望者的逃离 题解【贪心】【DP】

作者: wjyyy 分类: DP,解题报告 发布时间: 2018-05-12 22:20

点击量:51

    题目标签是 贪心+DP,但是实际上我是贪心+模拟出来结果的(不知道是不是数据弱了,欢迎dalao们hack
题解中有关贪心的内容我都会把它加粗变大
    定义一下
    s是距离,\(v=s/t\)是单位时间的速度,使用闪现的时候是\(v=60/1=60\),正常行走的时候是\(v=17/1=17\)。积攒一个闪现加上释放:最好情况是魔法在10或以上,\(v=60/1=60\);最坏情况是没有魔法:积攒和释放共需要4秒,平均速度v就是\(v=60/4=15\)。
    首先,有魔法(=10)的时候,一定要用闪现,这时速度是最快的,v=60,这里是贪心的一个点,尽可能让速度快。
    当魔法耗尽时(<10),有两种情况:
    1.剩余0~1,补充3次魔法可以用闪现,平均速度是v=60/4=15,能走60m,耗费4秒,但比行走慢;补充5次魔法可以用两次闪现,平均速度是v=120/7=17.14,能走120m,耗费7秒,比行走快。
    2.剩余2~9,补充1~2次魔法后可以用一次闪现,平均速度分别是\(v=60/2=30,v=60/3=20\),耗费2秒和3秒,都比行走快。
    因此,在以上两种情况中,离终点较远的情况下,闪现是比行走要快的,同理是贪心的思想。
    除此之外,我们还要特判快到终点(定为$s<68$)的情况,利用表格来说明
    | 剩余魔法 | 0~1 | 2~5 | 6~9 |效果|
    | 使用1次闪现 |耗时4s|耗时3s|耗时2s|距离60m|
    | 不使用闪现 |耗时1s|耗时1s|耗时1s|距离17m||
    列出下一次闪现需要几秒恢复:\(f(m)=(10-m-1)/4+2\)(算上使用的1s)向下取整
    所以f(0)=4,s=60而4s可以走(正常行走)68m
    f(1)=4,4s可以走68m
    因此在t>=4且s<68时正常行走就可以出去
    f(2)=3,4s可以走51m
    f(3)=3,f(4)=3,f(5)=3,f(6)=2,
    f(7)=2,f(8)=2,f(9)=2
    均同理
    以上判断方程为(sum最终结果,m因为在while循环中耗尽,m<10)
    \(if((9-m)/4+2>=((s-1)/17+1))\)
if(m<10&&t>=(s-1)/17+1&&(9-m)/4+2>=((s-1)/17+1))
{
    t-=(s-1)/17+1;
    s=0;
    break;
}
    \((9-m)/4+2\) 是使用闪现所耗费的总时间
    \(((s-1)/17+1))\)是行走耗费的总时间
    行走耗时更少的话当然是选择行走了,因为可以拆成更少的时间段来进行,举个栗子
| 剩余魔法 | Δm |1|
| 剩余距离 | Δs |18|
| 剩余时间 | Δt  |3|
    可以看出,当Δs=1$时,只需2s就可以直接走出去了,而补充魔法用闪现需要$4s$

    这里当然是选择贪2s了,这些思想在代码里都有体现。

Code:

#include<cstdio>
int main()
{
    int m,s,t,S,T;
    scanf("%d%d%d",&m,&s,&t);
    S=s;//S,T用来存初始值,方便最后一步算出结果
    T=t;
    while(s>0&&t>0)//循环的边界,也是最终判断的依据
    {
        if(m>=10)//当m>=10时,用闪现是最快的,没有之一,贪心思想
        {
            m-=10;
            s-=60;
            t--;
        }
        else if(m<10&&((9-m)/4+1)<t)//判断是休息还是直接开溜
        {
            if((9-m)/4+2>=((s-1)/17+1))//当能直接开溜的时候,贪心贪最小的
            {
                t-=(s-1)/17+1;
                s=0;
                break;
            }
            m+=4;
            t--;
        }
        else//不特判的情况,也不休息,直接正常行走,比如当t较小的时候
        {
            s-=17;
            t--;
        }
    }
    if(s<=0)
        printf("Yes\n%d\n",T-t);
    else if(t<=0)
        printf("No\n%d\n",S-s);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */