【2016.10.5NOIP普及模拟】wd的假日

发布于 2019-04-10  7 次阅读


题目描述

又到了十月一号了,今年十一居然是8天连休,wd早早的回到了家里,盘算着十月一号怎么过。作为一名dota狂热爱好者,打dota必然是他的首选任务。不过wd毕竟是学霸,作业还是要做的,书还是要看的。那么问题就来了,如何学习dota两不误。就个人管理而言,wd向来是饱受诟病的,于是他又想到了kk。wd告诉kk他在假期里想完成的n个学习任务,在这些任务中,他在这个假期至少要做m件,每件任务都有一个耗时,并且对于每个任务,wd都给出了一个好感度(顺便说一句,wd与zy是同一个中学的)。同时,这个假期的总时间是有限的,为T,他最少需要用来打dota的时间是t,而且,打dota的每个单位时间都有好感度g。现在,你要告诉wd,在至少打t时间dota,并完成至少m个任务的前提下,他所能获得的最大好感度。

输入

第一行两个整数n,m。
接下来n行每行两个整数ti,gi,表示每个任务的时间和好感度。
最后一行三个整数T,t,g。

输出

一行一个整数,表示最大好感度。如果没有符合的方案,则输出0。

思路

暴力枚举出每一种可能的方案,求出最优解就可以了

#include 
using namespace std;
int f[55],a[55],fl[55];
int n,m,tt,t,g,ans;
int max(int x,int y)
{
    return x>y?x:y;
}
int dfs(int dep,int x,int s,int l)
{
    if (l>=m)
    { 
        ans=max(ans,s+((tt-x)*g));
    }
    if (dep>n) return 0;
    dfs(dep+1,x,s,l);
    if (x+f[dep]<=tt-t&&fl[dep]==0&&dep!=1) 
    {
        fl[dep]=1;
        dfs(dep+1,x+f[dep],s+a[dep],l+1);
        fl[dep]=0;
    }
}
int main()
{
    freopen("holiday.in", "r", stdin);
    freopen("holiday.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&f[i],&a[i]);
    scanf("%d%d%d",&tt,&t,&g);   

    dfs(1,0,0,0);
    if (f[1]<=tt-t) dfs(1,f[1],a[1],1);
    printf("%d\n",ans);
    return 0;
}
]]>