小红笔试__牛客网

$\hspace{15pt}$ 小红正在参加一场编程笔试，整场考试共有 $n$ 道编程题。每道题包含若干测试用例，通过的用例数量与该题得到的分数成正比。

$\hspace{15pt}$ 对于第 $i$ 道题，小红有三种选择：
$\hspace{23pt}\bullet\,$ 写出暴力算法：耗时 $t_{i,b}$ ，可获得 $s_{i,b}$ 分；
$\hspace{23pt}\bullet\,$ 写出正确算法：耗时 $t_{i,a}$ ，可获得满分 $s_{i,a}$ ；
$\hspace{23pt}\bullet\,$ 放弃此题：不耗时且得分为 $0$ 。

$\hspace{15pt}$ 已知 $t_{i,b}\leqq t_{i,a}$ 且 $s_{i,b}\leqq s_{i,a}$ 。现给定笔试的总时长为 $T$ ，请你为小红规划做题方案，使得在不超过 $T$ 分钟的前提下，总得分最大。

$\hspace{15pt}$ 第一行输入两个正整数 $n,T\ \left(1\leqq n,T\leqq2000\right)$ ——题目数量与笔试总时长。

$\hspace{15pt}$ 接下来 $n$ 行，第 $i$ 行输入四个正整数 $t_{i,a},\ s_{i,a},\ t_{i,b},\ s_{i,b}$ （ $1\leqq t_{i,b}\leqq t_{i,a}\leqq2000$ ， $1\leqq s_{i,b}\leqq s_{i,a}\leqq10^5$ ），含义如下：
$\hspace{23pt}\bullet\,$ $t_{i,a}$ ：写出正确算法的耗时；
$\hspace{23pt}\bullet\,$ $s_{i,a}$ ：正确算法得分；
$\hspace{23pt}\bullet\,$ $t_{i,b}$ ：写暴力算法的耗时；
$\hspace{23pt}\bullet\,$ $s_{i,b}$ ：暴力算法得分。

$\hspace{15pt}$ 输出一个长度为 $n$ 的字符串，第 $i$ 个字符表示第 $i$ 题的策略：
$\hspace{23pt}\bullet\,$ 字符 $\tt A$ ——编写正确算法；
$\hspace{23pt}\bullet\,$ 字符 $\tt B$ ——编写暴力算法；
$\hspace{23pt}\bullet\,$ 字符 $\tt F$ ——放弃此题。

$\hspace{15pt}$ 要求输出方案的总耗时不超过 $T$ ，且总得分尽可能大。若存在多种方案能取得最高分，输出任意一种皆可。

$\hspace{15pt}$ 选择策略 $\tt AAB$ ：
$\hspace{23pt}\bullet\,$ 题 $1$ 写正确算法，耗时 $4$ ，得分 $10$ ；
$\hspace{23pt}\bullet\,$ 题 $2$ 写正确算法，耗时 $4$ ，得分 $20$ ；
$\hspace{23pt}\bullet\,$ 题 $3$ 写暴力算法，耗时 $1$ ，得分 $15$ 。

$\hspace{15pt}$ 总耗时 $4+4+1=9\leqq T$ ，总得分 $10+20+15=45$ ，可以证明该得分已达到最优。

#include <bits/stdc++.h> using namespace std; using ll=long long; int main() { ll n,t;cin >> n >> t; vector<vector<pair<ll,ll>>> timu(n+1,vector<pair<ll,ll>>(2));//题目; for(ll i=1;i<=n;i++) { ll tz,sz,tb,sb;cin >> tz >> sz >> tb >> sb; timu[i][0]={tz,sz}; timu[i][1]={tb,sb}; } vector<vector<ll>> dp(t+1,vector<ll>(n+1,0)); for(ll i=1;i<=n;i++) { for(ll j=t;j>=0;j--) { dp[j][i]=dp[j][i-1]; if(j>=timu[i][0].first) dp[j][i]=max(dp[j][i],dp[j-timu[i][0].first][i-1]+timu[i][0].second); if(j>=timu[i][1].first) dp[j][i]=max(dp[j][i],dp[j-timu[i][1].first][i-1]+timu[i][1].second); } } vector<char> ans; for(ll i=n;i>=1;i--) { if(t>=timu[i][0].first&&dp[t][i]==dp[t-timu[i][0].first][i-1]+timu[i][0].second) { ans.push_back('A'); t-=timu[i][0].first; } else if(t>=timu[i][1].first&&dp[t][i]==dp[t-timu[i][1].first][i-1]+timu[i][1].second) { ans.push_back('B'); t-=timu[i][1].first; } else ans.push_back('F'); } for(ll i=n-1;i>=0;i--) cout << ans[i]; } /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀ ⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀ ⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀ ⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀ ⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀ ⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀ ⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀ ⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀ ⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀ ⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧ ⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾ ⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀ ⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀ ⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀ */

小红笔试

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题