小白牛客月赛69C题开题顺序

[链接]https://ac.nowcoder.com/acm/contest/52441/C

题意：在一场比赛中，有n道题，总时长为t，错误罚分为p。每道题满分为a，时间系数为b，保底分为c，花费的时间x，错误提交次数y。如果总消耗的时间小于t，这道题的得分为max(c,a-x * b-y * p)。找到所有情况下的最大得分。

题解：用dfs深搜，dfs有两个参数，一个是得分，一个是消耗的时间，当消耗的时间大于总时长，返回。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 15;
const int mod = 1e9+7;
LL n,t,p;
LL a[N],b[N],c[N],x[N],y[N];
LL res;
bool st[15];

void dfs(LL ti,LL score)
{
    res = max(res,score);
    for(LL i=0;i<n;i++)
    {
        if(ti + x[i] <=t && st[i]==false)
        {
            st[i] = true;
            dfs(ti+x[i], score + max(c[i],a[i]- (ti + x[i]) * b[i] - y[i] * p));
            st[i]=false;
        }
    }
    
    
}

void solve()
{
    cin>>n>>t>>p;
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>x[i]>>y[i];
    }
    
    dfs(0,0);
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    while(T--)
    {
        solve();
    }
}