开氧气即过（亲测有用（
by hank0402 @ 2022-02-10 18:15:34
@[hank0402](/user/482642) 得了吧，你坐在我旁边，你让我开O2过了但是源代码TLE啊
by leoair @ 2022-02-10 18:21:50
毕竟你参考的tj也加了氧气瓶啊（
by hank0402 @ 2022-02-10 18:23:01
@[leoair](/user/124527)
```cpp
#include<bits/stdc++.h>
#define N 2501
using namespace std;
int m, n, cnt, s[N], head[N];
double res[N], f[N][N];
struct xcj{
double cost, fight;
} a[N];
struct xcx{
int to, nxt;
} e[N];
inline int read(){
int s = 0, w = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; w *= ch == '-' ? -1 : 1, ch = getchar());
for (; ch >= '0' && ch <= '9'; s = s * 10 + ch - '0', ch = getchar());
return s * w;
}
void add(int x, int y){e[++cnt] = {y, head[x]}, head[x] = cnt;}
void dp(int x, int fa){
s[x] = 1, f[x][1] = res[x];
for (register int i = head[x]; i; i = e[i].nxt){
int y = e[i].to;
if (y != fa){
dp(y, x), s[x] += s[y];
for (register int j = min(m, s[x]); j > 0; --j)
for (register int k = 0; k <= min(j - 1, s[y]); ++k) f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
}
}
}
bool chck(double mid){
res[0] = 0;
for (register int i = 1; i <= n; i+=2){
res[i] = a[i].fight - mid * a[i].cost;
res[i+1] = a[i+1].fight - mid * a[i+1].cost;
}
for (register int i = 0; i <= n; ++i)
for (register int j = 1; j <= m; j+=2){
f[i][j] = -1e9;
f[i][j+1] = -1e9;
}
dp(0, -1);
return f[0][m] >= 0;
}
int main(){
m = read() + 1, n = read();
for (register int i = 1; i <= n; i+=2){
a[i].cost = read(), a[i].fight = read(), add(read(), i);
a[i+1].cost = read(), a[i+1].fight = read(), add(read(), i+1);
}
double l = 0, r = 10000;
while (l < r - 1e-4){
double mid = (l + r) / 2;
if (chck(mid)) l = mid;
else r = mid;
}
printf("%.3lf", l);
}
```
事实证明，没 O2 也能过：<https://www.luogu.com.cn/record/68992233>
by Jerrlee✅ @ 2022-02-10 18:31:39
@[Jerrlee✅](/user/367652) 谢谢谢谢
请问register是优化了常数吗
by leoair @ 2022-02-10 18:39:35
@[leoair](/user/124527) 对，在循环中开 register 可以起到加速的作用
by Jerrlee✅ @ 2022-02-10 18:41:18
@[Jerrlee✅](/user/367652) 好的谢啦
互关嘛
by leoair @ 2022-02-10 18:42:27
@[leoair](/user/124527) OK
by Jerrlee✅ @ 2022-02-10 18:43:23