NC249073 开题顺序

NC249073 开题顺序

牛牛打 $CFCF$，已知一场比赛有 $nn$ 道题，第 $ii$ 道题的满分为 $a_{i}a\_i$，时间系数为 $b_{i}b\_i$，保底分为 $c_{i}c\_i$，本场比赛中每次错误提交罚 $pp$ 分。

即如果牛牛在第 $xx$ 分钟，这道题 $yy$ 次错误提交后通过第 $ii$ 题，他将获得 $max(ci,ai\mathrm{-}x\times bi\mathrm{-}y\times p)max(ci,ai-x\times bi-y\times p)$ 分。

比赛持续 $tt$ 分钟，请求出牛牛可能的最大得分。

一个朴素的深搜

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

long long n, t, p;
long long a[100], b[100], c[100], x[100], y[100];
long long vis[100];
long long ans = 0;

void clear()
{
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
}

//目前的时间，目前的分数
void dfs (long long now, long long grade)
{
    if (grade > ans)    ans = grade;

    for (int i = 1; i <= n; i++)
    {
        long long sc = max(c[i], a[i]-(now+x[i])*b[i]-y[i]*p);
        if (now + x[i] <= t && !vis[i])		//如果可以做这题
        {
            vis[i] = 1;
            dfs(now+x[i], grade+sc);
            vis[i] = 0;
        }
    }
    if (grade > ans)    ans = grade;
}

int main ()
{
    cin >> n >> t >> p;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i] >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)
    {
        clear();
        if (x[i] <= t)
        {
            vis[i] = 1;
            dfs(0, 0);
            vis[i] = 0;
        }
    }

    cout << ans << endl;

    return 0;
}