MnZn妹子求助 wqs二分,大佬们进来看看吧TAT
查看原帖
MnZn妹子求助 wqs二分,大佬们进来看看吧TAT
341034
abcde777楼主2021/7/10 20:26
#include<iostream>
#include<cstdio>
#include<cstring>
#define I inline
#define nnq nanachi
#define double long double
using namespace std;

const double eps = 1e-11;
const int N = 2010;
double f[N][N],ra[N],rb[N]; 
int n,a,b,useb[N][N];

I int dp(double cost) {
	memset(f,-0x3f,sizeof(f));
	memset(useb,0,sizeof(useb));
	for(int i=0;i<=a;++i) f[0][i]=0;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=a;++j) {
			useb[i][j]=useb[i-1][j];
			f[i][j]=f[i-1][j];
			if(!j) {
				double rate1=f[i][j],rate2=f[i][j]+rb[i]-cost;
				if(rate2>rate1) {
					f[i][j]=rate2;
					useb[i][j]=useb[i][j]+1;
				}
				continue;
			}
			if(f[i-1][j-1]+ra[i]>f[i][j]) {
				f[i][j]=f[i-1][j-1]+ra[i],useb[i][j]=useb[i-1][j-1]; 
			}
			double rate1=f[i-1][j-1]+ra[i]+rb[i]-ra[i]*rb[i]-cost,rate2=f[i-1][j]+rb[i]-cost;
			if(rate1>f[i][j]) {
				f[i][j]=rate1;
				useb[i][j]=useb[i-1][j-1]+1; 
			}
			if(rate2>f[i][j]) {
				f[i][j]=rate2;
				useb[i][j]=useb[i-1][j]+1; 
			}
		}
	}
	//cout<<useb[n][a]<<' '<<cost<<endl;
	if(useb[n][a]==b) return 0;
	else if(useb[n][a]>b) return 1;
	return -1;
}
I int read() {
	int ret=0; char ch;
	while((ch=getchar())>'9'||ch<'0'); ret=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+ch-'0';
	return ret;
}
int main()
{
	n=read(); a=read(); b=read();
	for(int i=1;i<=n;++i) cin>>ra[i];
	for(int i=1;i<=n;++i) cin>>rb[i];
	double l=0,r=1,ans=0;
	while((r-l)>=eps) {
		double mid=(l+r)*1.0/2;
		int mk=dp(mid);
		if(!mk) {
			r=mid;
			ans=max(ans,f[n][a]+mid*b);
		} else if(mk>0) {
			l=mid;
		} else {
			ans=max(ans,f[n][a]+mid*useb[n][a]);
			r=mid;
		}
	}
	cout<<ans<<endl;
	return 0;
}

WA在大点了,和答案差得不多(输出1030.26,out 1030.9329)求大佬们看看吧

2021/7/10 20:26
加载中...