题解都是将 -1 的情况拎出来单独跑dp。

为什么放在一起跑dp会挂。

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline bool _u(char x){return x>='0'&&x<='9';}
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	for(;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
	for(;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
	return x*f;
}
inline void write(int num,bool flag=0){
	static int st[39],tp=0;
	num<0&&(putchar('-'),num=-num);
	do st[++tp]=num%10;while(num/=10);
	while(tp) putchar(st[tp--]|48);
	putchar(flag?'\n':' ');
	return;
}
template<typename...Args>
inline void write(int t,Args...args){
	write(t),write(args...);
	return;
}
#define double long double
const int N=510;
const double inf=1e18+0.39393;

double dp[2][N][N];//表示前 i 个州，j 个助手，k 张选票的最小时间 
double ans=inf;
int n,K;
struct node{
	int a,b;
}a[N];

inline bool cmp(node x,node y){
	if(x.b==-1 && y.b==-1) return x.a>y.a;
	if(x.b==-1)return false;
	if(y.b==-1)return true;
	return x.b<y.b;
}

signed main(){
//	freopen("vote.in","r",stdin);
//	freopen("vote.out","w",stdout);
	n=read(),K=read();
	for(int i=1;i<=n;++i)a[i].a=read(),a[i].b=read();
	sort(a+1,a+n+1,cmp);
	bool f=0;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=n;++j)
			dp[f][i][j]=dp[f^1][i][j]=inf; 
	dp[f][0][0]=dp[f^1][0][0]=0;
	for(int i=1;i<=n;++i){
		f^=1;
		for(int k=K;k;--k){
			for(int j=min(i,k);~j;--j){ 
				dp[f][j][k]=dp[f^1][j][k];
				if(k>i)continue;
				if(a[i].b!=-1&&j)dp[f][j][k]=min(dp[f][j][k],dp[f^1][j-1][k-1]+1.0*a[i].b/j);
				dp[f][j][k]=min(dp[f][j][k],dp[f^1][j][k-1]+1.0*a[i].a/(j+1));
			}
		}
		for(int j=0;j<=i;++j) ans=min(ans,dp[f][j][K]);
//		cout<<i<<' '<<a[i].a<<' '<<a[i].b<<' '<<ans<<endl;
	}
	printf("%.15Lf\n",ans);
	return(39-39);
}

huck数据：

7
5
393 646
375 666
374 676
320 635
288 668
284 758
333 702