Problem
有 \(n\) 天，每天有 \(a_i\) 场比赛。
如果截止到第 \(i\) 天的胜率小于第 \(i-1\) 天的胜率，乐乐就会在第天心情变得更好；否则，他的心情会变得更糟。其中，第 \(i\) 天的胜率指的是，当 \(i=0\) 时为 \(0\)，否则指的是第 \(i\) 天之前玩游戏赢的次数总和除以第 \(i\) 天之前玩游戏的次数总和所得的值。
已知这 \(n\) 天，乐乐总共赢了 \(k\) 次。求乐乐最多能开心多少天。
\(60 \%\) 的数据：\(n,a_i \le 100\)
\(100 \%\) 的数据：\(n \le 2000, 1 \le a_i \le 5 \times 10^5, 0 \le k \le a_1+a_2+...+a_n\)
Input
第一行两个整数 \(n\) 和 \(k\)。
接下来一行 \(n\) 个数，第 \(i\) 个数表示 \(a_i\)。
Output
一行一个整数，表示乐乐最多能开心几天。
Sample
Input 1
5 7
2
3
7
4
9
Output 1
3
Input 2
3 5
1
2
2
Output 2
1
Input 3
2 4
2
10
Output 3
1
Input 4
10 12
2
8
3
5
10
5
2
9
19
22
Output 4
7
Solution
考虑朴素做法。
我们设 \(f_{i,j}\) 表示前 \(i\) 天赢了 \(j\) 场比赛最多的开心次数，记 \(s_i\) 表示前 \(i\) 天比赛总场数。接下来我们分情况讨论：
- 第 i 天不开心，那么 \(f_{i,j} = \max f_{i-1,p}\)，其中 \((0 \le p \le j)\)。
- 第 i 天开心，那么 \(f_{i,j} = \max f_{i-1,p}\)，其中 \(p\) 满足 \(\dfrac{p}{s_{i-1}} < \dfrac{j}{s_i}\)，即 \(p < \dfrac{j \times s_{i-1}}{s_i}\)。
观察到两种情况均为前缀 \(max\)，并且第 \(i\) 天的状态只与第 \(i-1\) 天有关，因此我们在求完每一天的答案后重新求前缀 \(max\)，就可用来求解下一天的答案了。
注意第二种情况是 \(<\)，所以求 \(p\) 时先要减去一个极小数再将其下取整。
最后输出 \(f_{n,k}\) 即可，时间复杂度 \(O(nk)\)。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 105;
const int kmaxM = 1e4 + 3;
int n, k, a[kmax], s[kmax];
int p[kmax];
int f[kmax][kmaxM], g[kmaxM];
int res;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] + s[i - 1];
}
if (k == s[n]) {
cout << 1;
return 0;
}
for (int i = 1; i <= k; i++) {
f[1][i] = g[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int l = floor(1.0 * j * s[i - 1] / s[i] - 0.01);
f[i][j] = max(f[i][j], g[j]);
f[i][j] = max(f[i][j], g[l] + 1);
}
for (int j = 1; j <= k; j++) {
g[j] = max(g[j - 1], f[i][j]);
}
}
cout << f[n][k] << '\n';
return 0;
}
接下来考虑满分做法。
我们观察到整个状态上一共有三个属性，天数、赢比赛的次数和最多的开心次数，朴素算法之所以慢，是因为 \(a_i\) 较大，从而导致 \(k\) 很大。
但如果我们换种角度看，将天数和开心次数记为状态，赢的次数记为值，就发现无论是时间还是空间都可以跑过了。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 2005;
int n, k, a[kmax], s[kmax];
long long f[kmax];
int res;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] + s[i - 1];
}
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = 1e9;
}
for (int i = 2; i <= n; i++) {
for (int j = i; j; j--) {
long long l = 1ll * f[j - 1] * a[i] / s[i - 1] + 1;
if (l > a[i])
continue;
f[j] = min(f[j], f[j - 1] + l);
}
}
for (int i = n; ~i; i--) {
if (f[i] <= k) {
cout << i;
break;
}
}
return 0;
}