# 比赛胜率()-其他

## 比赛胜率()

### Problem

$$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 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

• 第 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}$$。

#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;
}


#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;
}

————————

### Problem

$$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 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

• 第 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}$$。

#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;
}


#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;
}