样例过0分WA求条
查看原帖
样例过0分WA求条
1546776
llzlqbg1楼主2025/8/29 16:20
#include<bits/stdc++.h>
using namespace std;
const int N=35;
double k[N],dp[N][N],kk,c,q[N];
int n,s[N],sum=0;
int main(){
	cin>>n>>kk>>c;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		sum+=s[i];
	}
	for(int i=1;i<=n;i++){
		k[i]=s[i]*1.0/sum*1.0;
		q[i]=q[i-1]+k[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=k[i]*(kk+c);
	}
	for(int i=2;i<=n;i++){
		dp[i-1][i]=min(k[i-1],k[i])*(kk*2+c)+max(k[i-1],k[i])*(kk+c);
	}
	for(int len=3;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			dp[i][j]=1e6;
			for(int d=i+1;d<j;d++){
				dp[i][j]=min(dp[i][j],dp[i][d-1]+dp[d+1][j]+(q[j]-q[i-1]-k[d])*kk+k[d]*(kk+c));
			}
		}
	}
	cout<<fixed<<setprecision(3)<<dp[1][n]<<endl;
}
2025/8/29 16:20
加载中...