https://www.luogu.com.cn/problem/P8162

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

const int MAXN = 500 + 7;
const double INF = 1e9;

struct state {
	double a;
	double b;
} a[MAXN];

int n, m;
double dp[2][MAXN][MAXN]; // dp_i_j_k 将州按 b排序后考虑到第 i个州时有 j张票与 k个协助者的最小时间花费 

template<typename T_int>
void input(T_int &x) {
	char ch = getchar();
	T_int fu = 1; x = 0;
	while(!('0' <= ch && ch <= '9')) fu = ((ch == '-') ? -1 : fu), ch = getchar();
	while('0' <= ch && ch <= '9') x = x * 10 + (ch - '0'), ch = getchar();
	x *= fu;
}

bool cmp(state x, state y) {return (x.b != y.b) ? (x.b < y.b) : (x.a < y.a);}

int main() {
	input(n); input(m); int x, y;
	for(int i=1; i<=n; i++) input(x), input(y), a[i] = (state){1.00*x, (~y ? 1.00*y : INF)};
	
	for(int j=0; j<=m; j++) {
		for(int k=0; k<=j; k++) dp[0][j][k] = dp[1][j][k] = INF;
	}
	
	sort(a+1, a+1+n, cmp);
	
	dp[0][0][0] = 0.00;
//	printf("test = %lf\n\n", dp[0][0][1]);
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=min(i, m); j++) {
			for(int k=0; k<=j; k++) {
//				printf("i = %d, j = %d, k = %d, a[i].a = %lf, a[i].b = %lf\n", i, j, k, a[i].a, a[i].b);
				if(j != i) dp[1][j][k] = min(dp[1][j][k], dp[0][j][k]); // , puts("HERE - 1");
				if(j && j-1 >= k) dp[1][j][k] = min(dp[1][j][k], dp[0][j-1][k] + a[i].a / (k+1)); // , puts("HERE - 2");
				if(j && k) dp[1][j][k] = min(dp[1][j][k], dp[0][j-1][k-1] + a[i].b / k); // , puts("HERE - 3");
//				printf("dp[1][j][k] = %lf, dp[0][j][k] = %lf, dp[0][j-1][k] = %lf, a[i].a / (k+1) = %lf, dp[0][j-1][k-1] = %lf, a[i].b / k = %lf\n\n", dp[1][j][k], dp[0][j][k], dp[0][j-1][k], a[i].a / (k+1), dp[0][j-1][k-1], a[i].b / k);
			}
		}
		for(int j=0; j<=m; j++) {
			for(int k=0; k<=j; k++) dp[0][j][k] = dp[1][j][k], dp[1][j][k] = INF;
		}
	}
	
	double ans = INF;
	for(int k=0; k<=m; k++) ans = min(ans, dp[0][m][k]);
	
	printf("%.15f", ans);
	
	return 0;
}

https://www.luogu.com.cn/record/list？pid=P8162&user=425912