题目描述

又到了十月一号了，今年十一居然是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;
}