Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32916 | liuziming | 【S】T1 | C++ | 运行超时 | 60 | 1000 MS | 76028 KB | 1155 | 2024-10-02 14:32:28 |
#include<bits/stdc++.h> using namespace std; int n,m,a[20010]; bool cmp(int a,int b){ return a<b; }long double dp[2010][5010],ans,nxt[20010]; queue<pair<int,int> > state; bool vis[2010][5010]; int main(){ //freopen("monster.in","r",stdin); //freopen("monster.out","w",stdout); //ios::sync_with_stdio(0); cin>>n>>m; //cout<<n<<m<<'\n'; for(int i=1;i<=n;i++){ cin>>a[i]; }sort(a+1,a+n+1,cmp); // for(int i=1;i<=n;i++){ // cout<<a[i]<<' '; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ dp[i][j]=1e9; } } dp[0][m]=ans=n; //cout<<ans<<'\n'; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=m-a[j];k>=0;k--){ long double nowans=((long double)(j)/(long double)n); int lastk=k+a[j]; if(dp[i-1][lastk]==1e9) continue; //printf("%.10Lf %d %d\n",dp[i-1][lastk],a[j],lastk); dp[i][k]=min(dp[i-1][lastk]-nowans,dp[i][k]); ans=min(dp[i][k],ans); } } } printf("%.10Lf",ans); }