Codeforces 1056F Write The Contest
题目链接
http://codeforces.com/contest/1056/problem/F
题目大意
有 $n$ 个题，每个题的难度为 $a_i$ ，分数为 $p_i$ ，你的最初的水平评级为 $s$ ，每做一道题需要 $s / a_i$ 时间，且每做一道题之前，你需要先花费 $10$ 分钟准备，准备后你的水平评级会变成 $0.9s$ 。你可以选择在任何时间进行学习，学习 $t$ 分钟会使水平评级增加 $C \cdot t$ 。问 $T$ 时间内最大的得分为多少。
题目分析
显然可知，先学习之后再一口气做题能使得获得的水平评分得到更充分的利用。且显然如果要做几道题，那么先做更难的题速度更快。因此先对所有的题目按照难度排序。之后考虑如何去求解最长时间。考虑到固定的几个题所用的时间是 $T = \sum\limits_{i=1}^{k}{(\frac{a_i}{(0.9) ^ {i} s} + 10)}$ ，可以将 $s$ 提取出来，有用时 $T = \frac{1}{s} \sum\limits_{i=1}^{k}{(\frac{a_i}{(0.9) ^ {i}})} + 10k$ 。
设 $T ^ {*} = \sum\limits_{i=1}^{k}{(\frac{a_i}{(0.9) ^ {i}})}$
因此可以设 $f[i][j][k]$ 为最后一个选的是 $i$ 题，一共选择了 $j$ 道题，且总分为 $k$ 且有 $T ^ {*}$ 最小，利用背包的简单优化可以将空间复杂度优化掉一维。最后对于每一种情况，使用三分法得到使得所花费时间最短的需要学习的时间，验证是否在题目要求时间内即可
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n, m, tc;
double c, t;
double a[105];
int p[105];
double f[105][1005];
pair <double, int> sr[105];
double s[105];
int read(){
int x;
scanf("%d", &x);
return x;
}
bool cmp(pair <double, int> x, pair <double, int> y){
return x > y;
}
double check(double x, double y){
return x + y / (1.0 + x * c);
}
double getn(double x){
double l = 0, r = t;
double lmid, rmid;
for(int i=1;i<=50;i++){
lmid = (2.0 * l + r) / 3.0;
rmid = (l + 2.0 * r) / 3.0;
if(check(lmid, x) > check(rmid, x)){
l = lmid;
}else{
r = rmid;
}
}
return check(l, x);
}
int solve(){
int i, j, k;
double inf = 1e18;
int ans = 0;
for(i=0;i<=n;i++){
for(j=0;j<=n*10;j++){
f[i][j] = inf;
}
}
f[0][0] = 0;
s[0] = 1.0;
for(i=1;i<=n;i++){
s[i] = s[i - 1] / 0.9;
}
for(i=1;i<=n;i++){
for(j=i;j>0;j--){
for(k=n*10-p[i];k>=0;k--){
f[j][k + p[i]] = min(f[j][k + p[i]], f[j - 1][k] + s[j] * a[i]);
}
}
}
for(i=1;i<=n;i++){
for(j=0;j<=n*10;j++){
if(i * 10 + getn(f[i][j]) <= t){
ans = max(ans, j);
}
}
}
printf("%d\n", ans);
return 0;
}
int main(){
int i, j;
tc = read();
while(tc--){
n = read();
scanf("%lf%lf", &c, &t);
for(i=1;i<=n;i++){
sr[i].first = read();
sr[i].second = read();
}
sort(sr + 1, sr + n + 1, cmp);
for(i=1;i<=n;i++){
a[i] = sr[i].first;
p[i] = sr[i].second;
}
solve();
}
return 0;
}