Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
32998 liuziming 【S】T1 C++ 通过 100 849 MS 2940 KB 1411 2024-10-02 17:13:42

Tests(11/11):


#include<bits/stdc++.h> using namespace std; int n,m,a[20010],i,k,j,lastk; bool cmp(int a,int b){ return a<b; }long double dp[2010][5010],ans,nxt[20010],nowans; 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); scanf("%d %d",&n,&m); //cout<<n<<m<<'\n'; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); }sort(a+1,a+n+1,cmp); // for(int i=1;i<=n;i++){ // cout<<a[i]<<' '; dp[0][0]=ans=0; //cout<<ans<<'\n'; int cnt=0,nown=n,last=0; while(nown){nown>>=1;cnt++;} for(int pos=cnt;pos>=1;pos--){ if((1<<(pos-1))&n){ for(int j=0;j<=n;j++){ for(int k=a[j];k<=m;k++){ long double nowans=((long double)(j)); dp[last+1][k]=max(dp[last][k-a[j]]+nowans,dp[last+1][k]); ans=max(ans,dp[last+1][k]); } }last++; }if(pos!=1){ for(int k=0;k<=m;k++){ for(int k1=0;k1<=k;k1++){ int k2=k-k1; dp[2*last][k]=max(dp[2*last][k],dp[last][k1]+dp[last][k2]); ans=max(ans,dp[2*last][k]); } }last*=2; } } printf("%.10Lf",(long double)n-ans/(long double)n); }


测评信息: