Problem Description:
又到了选课的时间啦。大一萌新小小怪下士第一次选课没有制定好高效的策略,导致第一学期的学分不高,他想在第二学期获得尽可能多的学分,因此作为小小怪下士的上司搭档兼朋友的你,大大怪将军,需要帮助小小怪下士做出最优的选择。
当然,小小怪上学可不是在地球,他们的母星白天拥有48个小时,上课时间在12:00到24:00(此时母星只到了一天的中间哦)之间。你知道所有可选的课程的时间,也知道相应课程的学分,所有课程时长均为1h。
ps:每连续上3小时课小小怪就需要休息1h。
你仅需计算出可得的最高学分。无需给出你所选课程的安排。
Sample Input:
10
1 12
2 12
2 17
1 18
2 16
1 16
1 20
1 13
1 17
2 18
Sample Output:
10
AC代码:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<set>
#include<string.h>
using namespace std;
int c[30];
int dfs(int now,int cnt) ///当前课时,连续课程计数
{
if(now==23) return 0;///递归出口,返回的是0,学分是在外面c[now]加上去的
if(cnt==3) return dfs(now+1,0);///如果计数累计到3门课,则推后一门课,没有加学分。
return max( c[now]+dfs(now+1,cnt+1), dfs(now+1,0));
/// 选课则加分计数 否则不加分计数清零
}
int main()
{
int n,k,t;
while(scanf("%d",&n)!=-1)
{
memset(c,0,sizeof(c));
while(n--)
{
scanf("%d%d",&k,&t);
c[t]=max(c[t],k);
}
printf("%d
",dfs(12,0));
}
return 0;
}