Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
32916 liuziming 【S】T1 C++ 运行超时 60 1000 MS 76028 KB 1155 2024-10-02 14:32:28

Tests(6/10):


#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); }


测评信息: