gdufe1534-小小怪一定认真听课-dfs

Problem Description:

又到了选课的时间啦。大一萌新小小怪下士第一次选课没有制定好高效的策略，导致第一学期的学分不高，他想在第二学期获得尽可能多的学分，因此作为小小怪下士的上司搭档兼朋友的你，大大怪将军，需要帮助小小怪下士做出最优的选择。

当然，小小怪上学可不是在地球，他们的母星白天拥有48个小时，上课时间在12：00到24：00（此时母星只到了一天的中间哦）之间。你知道所有可选的课程的时间，也知道相应课程的学分，所有课程时长均为1h。

ps：每连续上3小时课小小怪就需要休息1h。

你仅需计算出可得的最高学分。无需给出你所选课程的安排。

Input:

要求多组输入。第一行包含一个可选课程的数量整数N（1<=N<=30），以下N行每行包括用空格分隔的两个整数：学分k(0<=k<=2)，该课程的上课时间t (12<=t<=23)

Output:

输出最优解时的最高学分。

Sample Input:

Sample Output:

10

AC代码：

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<set>

#include<string.h>

using namespace std;

int c[];

int dfs(int now,int cnt) ///当前课时，连续课程计数

{

    if(now==) return ;///递归出口，返回的是0，学分是在外面c[now]加上去的

    if(cnt==) return dfs(now+,);///如果计数累计到3门课，则推后一门课，没有加学分。

    return max( c[now]+dfs(now+,cnt+), dfs(now+,));

                /// 选课则加分计数         否则不加分计数清零

}

int main()

{

    int n,k,t;

    while(scanf("%d",&n)!=-)

    {

        memset(c,,sizeof(c));

        while(n--)

        {

            scanf("%d%d",&k,&t);

            c[t]=max(c[t],k);

        }

        printf("%d\n",dfs(,));

    }

    return ;

}

巴特西

gdufe1534-小小怪一定认真听课-dfs

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章