SolutionN≤500N\le 500N≤500我们需要O(N3)O(N^3)O(N3)的算法。直接状压 dp 至少O(2N)O(2^N)O(2N)我们一定有大量最优解的性质没有找到。为了方便约定一个州有三种状态B 类点演讲至BiB_iBi小时同时获得选票和协作者。A 类点演讲至AiA_iAi小时只获得选票。无效点不去演讲时间为000。对于Bi−1B_i-1Bi−1的州不妨令Bi∞B_i\inftyBi∞。我们来找一些最优解的性质性质 1不会出现并行演讲的情况任意时刻所有人一定在一起演讲。设目前共有ppp人则这一时刻演讲速度恒为ppp。相比并行演讲我们完全可以让这ppp个人集中到同一个尚未完成的州中。这样不仅不会增加完成所有目标所需的时间而且如果集中演讲刚好获得了新的协作者之后的演讲速度还会更快。因此存在最优方案使得在每个时刻所有人都在同一个州演讲。性质 2不会出现 A 类点排在 B 类点前面的情况。临项交换论证即可。性质 3B 类点一定按照BBB从小到大的顺序做。证明考虑临项交换不妨设i,ji,ji,j相邻此前共有aaa个人。先做iiiBia1Bja2\frac{B_i}{a1}\frac{B_j}{a2}a1Bia2Bj先做jjjBja1Bia2\frac{B_j}{a1}\frac{B_i}{a2}a1Bja2Bi上减下得(Bi−Bj)(1a1−1a2)0 \left(B_i-B_j\right)\left(\frac{1}{a1}-\frac{1}{a2}\right)0(Bi−Bj)(a11−a21)0性质 4如果iii是 B 类点那么所有满足BjBiB_jB_iBjBi的点jjj都一定不是无效点。调整法证明。如果出现上述情况那么令jjj变成 B 类点iii变成无效点一定更优。这些性质够了。O(N3)O(N^3)O(N3)的复杂度启发我们 dp。我们需要钦定kkk个 B 类点按BBB值从小到大做再从剩下的州里选m−km-km−k个AAA值最小的作为 A 类点做我们考虑先把州按BBB从小到大排序。发现kkk对统计 A 类点的贡献系数有很大影响我们考虑外层枚举kkk。此时不难得到一个O(N4)O(N^4)O(N4)的算法设fi,a,bf_{i,a,b}fi,a,b表示前iii个州选了aaa个 A 类点bbb个 B 类点的最小时间。结合性质 4我们发现最后一个BBB类点前面一定没有无效点。因此我们枚举最后一个BBB类点的位置并把序列拆成前后两部分。前半部分满足abiabiabi状态数减少。即fi,bf_{i,b}fi,b表示前iii个点全部选入有bbb个 B 类点的最小时间。fff主要是在决定前缀中的哪些州是 B、哪些是 A真实时间顺序由性质 2、3 自动确定。后半部分也可以O(n2)O(n^2)O(n2)预处理详见代码中g数组。此时总时间复杂度已经优化到了O(N3)O(N^3)O(N3)可以通过。Code#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#defineper(i,a,b)for(inti(a);ib;--i)#definerept(i,a,b)for(inti(a);ib;i)#definepert(i,a,b)for(inti(a);ib;--i)#definefifirst#definesesecond#definedbdouble#defineme(x,y)memset(x,y,sizeof(x))usingnamespacestd;usingElempairdb,db;constexprintN502;constexprdb INF1e32;Elem x[N];db f[N][N],g[N][N],ans;intn,m;inlinevoidupd(dbx,db y){xmin(x,y);}// f[i][b]: 前i个点全部选入有b个B类点的最小时间// g[i][j]: 在i~n中选j个A类点的最小值signedmain(){cin.tie(0)-sync_with_stdio(0);cinnm;rept(i,1,n){cinx[i].fix[i].se;if(x[i].se0)x[i].seINF;}sort(x1,xn1,[](constElemx,constElemy){returnx.sey.se;});me(g,100);// 统一赋值成一个很大的数g[n1][0]0;pert(i,n,1){rept(j,0,n-i1){if(j)upd(g[i][j],g[i1][j-1]x[i].fi);upd(g[i][j],g[i1][j]);}}ansg[1][m];rept(k,1,m){me(f,100),f[0][0]0;rep(i,0,n)rept(b,0,min(i,k)){upd(f[i1][b1],f[i][b]x[i1].se/(b1));// B类点upd(f[i1][b],f[i][b]x[i1].fi/(k1));// 这个A类点实际在最后做那时已经有k1个人。}rept(i,k,m)upd(ans,f[i][k]g[i1][m-i]/(k1));// 枚举最后一个b类点的位置更新答案}coutformat({:.15f},ans);return0;}