当前位置: 首页 > 工具软件 > Survive > 使用案例 >

【NOIP_模拟题】survive

姚棋
2023-12-01

【数据资源】链接:http://pan.baidu.com/s/1hrANd1i 密码:uicz
【题目名称】survive
【时间限制】1000ms
【空间限制】128M
【题目描述】
子曰:不睡觉就会死。
深信此话的LYM决定在本学期接下来的n节课上考虑一下睡觉的问题。LYM认为如果在一堂课上睡觉,身体的疲劳值就会下降,反之如果在一堂课上不睡觉,身体的疲劳值就会上升。而身体对疲劳的忍耐是有限度的,一旦疲劳值超过限度,LYM就会go die,于是他不得不在一些课上睡觉。注意,LYM的疲劳值只会在一节课上完后发生改变,如果上完最后一节课后,疲劳值超出了限度,LYM仍然会go die。
不过,在不同的课上,疲劳值的变化量并不总是一样,就如在班主任的课上睡觉,疲劳值并不会下降太多,因为那样会睡得很不安心。
但是,LYM是一个死要面子的人,他宁可冒着生命危险,也要挽回自己在老师心中的形象,因此他不能总是在人家的课上睡觉。他给自己定下了一个规矩:决不连续地在同一主科的课上睡觉,即如果LYM在主科X的某堂课上睡了觉,那么在下一堂(不一定是相邻的)主科X的课上,LYM就绝不会睡觉。
经过了这n节课后,LYM竟然没有死,LYM想知道自己对疲劳值的忍耐极限至少是多少。
【输入格式】
第一行,一个正整数n.
第二行,n个正整数,表示这n节课的课程安排。每个整数代表一门课程,科目代号对应关系参见下文的表格。(1~6号学科均为主科,7号学科不算作主科).
第三行,n个正整数,其中第i个数表示在第i节课上睡觉,疲劳值的减少量。
第四行,n个正整数,其中第i个数表示在第i节课上不睡觉,疲劳值的增加量。
第五行,一个整数,表示LYM的初始疲劳值。如果初始疲劳值大于了忍耐限度,LYM会在第一节课前就暴亡。

科目语文数学英语物理化学生物其他
代号1234567

【输出格式】
一个整数,表示LYM的忍耐限度的最小可能值。
【样例输入1】
3
6 6 7
3 4 5
5 4 3
-1
【样例输出1】
0
【样例说明1】
第1,3节课睡觉;
第2节课不睡觉.
【样例输入2】
5
7 4 4 5 4
1 6 6 4 4
6 3 8 7 7
8
【样例输出2】
9
【样例说明2】
第1,2,4,5节课睡觉;
第3节课不睡觉.
【数据范围】
对于20%的数据,有且仅有一门主科。
对于100%的数据,1<=n<=5000,第三,四行的数据保证大于等于0.
保证所有输入和输出都在[-2000000000,2000000000]范围内.
没有说明是正整数的数据不保证为正。

题解

解法提示
  1. 此题要求最优解,显然是一道动态规划;
  2. 此题要求不能连续在同一主科的课上睡觉,最好的解决后效性的方法就是采用状态压缩;
  3. 此题要求忍耐限度最小值 ,是典型的二分法的标志,二分答案+DP验证:具体操作就是在状态转移的过程中,将已经不合法的状态舍去,不进行下一步的转移;
  4. 此题不用二分答案,理论上是不对的,但是实际测试中,某些错解可以骗到大部分的分。
  5. 时间复杂度O(64n*log S)S为二分答案的上限。
    多说无益,具体转移方程已经细节参见代码:
#include<cstdio>
#include<cstring>
#define MAXN 15500
#define inf 0x3fffffff
int a[MAXN],d[MAXN],u[MAXN],init,n,f[MAXN][70];
int minn(int x,int y)
{
    return x<y?x:y;
}
bool dp(int lim)
{
    for(int i=0;i<=63;i++)
    {
        f[0][i]=inf;//事实上,赋值为于init也是可行的;
    }
    f[0][0]=init;
    int tmp;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>6)
        {
            for(int s=0;s<=63;s++)
            {
                f[i][s]=inf;
                if(f[i-1][s]<=lim)
                {
                    f[i][s]=f[i-1][s]-d[i];
                }
            }
        }
        else
        {
            tmp=1<<(a[i]-1);
            for(int s=0;s<=63;s++)
            {
                f[i][s]=inf;
                if((s>>(a[i]-1))&1)
                {
                    if(f[i-1][s^tmp]<=lim)
                    {
                        f[i][s]=f[i-1][s^tmp]-d[i];
                    }
                }
                else
                {
                    if(f[i-1][s]<=lim)
                    {
                        f[i][s]=f[i-1][s]+u[i];
                    }
                    if(f[i-1][s^tmp]<=lim)
                    {
                        f[i][s]=minn(f[i][s],f[i-1][s^tmp]+u[i]);
                    }
                }
            }
        }
    }
    for(int s=0;s<=63;s++)
    {
        if(f[n][s]<=lim)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    freopen("survive.in","r",stdin);
    freopen("survive.out","w",stdout); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u[i]);
    }
    scanf("%d",&init);
    int L=init,R=inf,M;
    while(L<=R)
    {
        M=(L+R)>>1;
        if(dp(M))
        {
            R=M-1;
        }
        else
        {
            L=M+1;
        }
    }
    printf("%d",L);
    fclose(stdin);
    fclose(stdout); 
    return 0;
}

以上是正解

 类似资料: