@[LiM_817](/space/show?uid=56724) 随机化了就不需要dp吧qwq 似乎直接贪心即可。
然后我们就可以随机多次。
另外 STO [LiM_817](/space/show?uid=56724) tql
by 花里心爱 @ 2019-04-17 22:29:10
sto是不是随机完了贪心鸭
~~感觉贪心应该比dp还好写吧QAQ~~
by 我不认识你 @ 2019-04-17 23:10:23
lmyakioi
by NaCly_Fish @ 2019-04-17 23:43:42
@[LiM_817](/space/show?uid=56724)
用随机贪心吧qwq
无耻的宣传一波：[link](http://m-sea-blog.com/archives/734/)
by M_sea @ 2019-04-18 08:12:07
# UAKIOI
by Smile_Cindy @ 2019-04-18 08:30:58
模拟退火改爬山就好
by iostream @ 2019-04-18 11:57:33
@[LiM_817](/space/show?uid=56724) 我的岁几乎87ms
by ecnerwaIa @ 2019-06-03 17:45:13
@[LiM_817](/space/show?uid=56724) 随机化。打错了qwq
by ecnerwaIa @ 2019-06-03 17:45:37
@[LiM_817](/space/show?uid=56724) @[Irressey](/space/show?uid=79017) @[我不认识你](/space/show?uid=111380) @[iostream](/space/show?uid=13052) @[M_sea](/space/show?uid=38370) 此题随机化贪心+dp可以做到总时限84ms。
附上代码（说真的自从发现了这个套路后好多题都被我这个方法乱搞过了）。
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=22,inf=1<<30;
int n,k,s[N],w[N];
double ave,dp[N][7];
inline int min(int a,int b){return a<b?a:b;}
inline double sqr(double x){return x*x;}
inline double calc(){
static int p,i,j,d;
for(i=1;i<=n;++i)s[i]=w[i]+s[i-1];
for(i=1;i<=n;++i){
p=min(k,i);
dp[i][1]=sqr(s[i]-ave);
for(j=2;j<=p;++j){
dp[i][j]=inf;
for(d=1;d<i;++d){
dp[i][j]=min(dp[i][j],dp[d][j-1]+sqr(s[i]-s[d]-ave));
}
}
}
return dp[n][k];
}inline void work(){random_shuffle(w+1,w+1+n);}
int main(){
srand(time(NULL));
scanf("%d%d",&n,&k);
int i,j;
for(i=1;i<=n;++i)scanf("%d",&w[i]),ave+=w[i];
ave=ave/k;
work();
double ans=calc(),pre;
int T=10,G;
while(T--){
G=7;
work();
ans=min(ans,calc());
while(G--){
for(i=1;i<=n;++i)
for(j=1;j<i;++j){
swap(w[i],w[j]);
pre=ans;
ans=calc();
if(pre<ans)swap(w[i],w[j]),ans=pre;
}
}
}
printf("%.2lf\n",sqrt(ans*1.0/k));
return 0;
}
```
by ecnerwaIa @ 2019-06-03 17:49:27
如果觉得不保险的话，随机个100-200次都没问题，那样总时限也才840-1680ms 左右
by ecnerwaIa @ 2019-06-03 17:50:11