谁能帮我调一下提高一下时间复杂度
  • 板块灌水区
  • 楼主末然Ender
  • 当前回复24
  • 已保存回复24
  • 发布时间2024/7/20 15:53
  • 上次更新2024/7/20 16:42:58
查看原帖
谁能帮我调一下提高一下时间复杂度
339728
末然Ender楼主2024/7/20 15:53
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T& x){x=0;char ch=getchar();long long f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}
template<typename T,typename... Args>
void read(T& first,Args&... args){read(first);read(args...);}
template<typename T>
void write(T arg){T x=arg;if (x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');}
template<typename T,typename... Args>
void write(T& arg,Args&... args){write(arg);if(sizeof...(args) !=0){putchar(' ');write(args...);}}
typedef long long ll;
const int N=3e4+2;
vector<vector<ll> > f(N+1,vector<ll>(1005)),cl(N+1,vector<ll>(1005));
int func(ll n,ll k,ll target) {
    ll minN = min(k,target);
    ll targetMax = n * k;
    f=cl;
    for(int i = 1;i<=minN;i++){
        f[1][i]=1;
    }
    for(int i = 2;i<=n;i++){
        for(int j = i;j<=targetMax;j++){
            for(int l = 1;l<=j && l<=k;l++){
                f[i][j] = (f[i][j] + f[i - 1][j - l]);
			}
        }
    }
    return f[n][target];
}
int n,m;
int a[N],fc[N];
double v;
ll sum;
int main(){
	freopen("1.in","r",stdin);
	read(n,m);
	for(int i=1;i<=n*m;i++){
		read(a[i]);
	}
	for(int i=n;i<=n*m;i++){
//		cerr<<i<<'/'<<n*m<<endl;
		fc[i]=func(n,m,i);
		sum+=fc[i];
	}
	for(int i=n;i<=n*m;i++){
		v+=(1.0*(1ll*a[i]*fc[i]))/(1.0*sum);
	}
	printf("%.2lf",v);
	return 0;
} 

自设题目(无数据)

2024/7/20 15:53
加载中...