90分WA最后一点求调QWQ
查看原帖
90分WA最后一点求调QWQ
90971
智子·起源楼主2022/1/14 15:17

RT

#include<bits/stdc++.h>
using namespace std;
int n,c,sum[1000+5];
int f[1000+5][1000+5][2],a[1000+5];
int By_Zephyr;
struct data{
	int x,v;
}t[1000+5];
bool cmp(data a,data b){
	return a.x<b.x;
}
int main(){
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		t[i].x=a[i];
	}
	for(int i=1;i<=n;++i){
		int TMP;
		cin>>TMP;
		By_Zephyr+=TMP;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&t[i].v);
	}
	a[++n]=c,t[n].x=c,t[n].v=0;
	sort(a+1,a+1+n);
	sort(t+1,t+1+n,cmp);
	for(int i=1;i<=n;++i)sum[i]=sum[i-1]+t[i].v;
	
	for(int i=0;i<1000+5;++i)
		for(int j=0;j<1000+5;++j)
			f[i][j][0]=f[i][j][1]=2100000000;
	for(int i=1;i<=n;++i)
		if(a[i]==c){
			f[i][i][0]=f[i][i][1]=0;
			break;
		}
	
	for(int l=2;l<=n;++l){
		for(int i=1;i<=n-l+1;++i){
			int j=i+l-1;
			f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]));
			f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));
			f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]));
			f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
		}
	}
	int ans=min(f[1][n][0],f[1][n][1]);
	printf("%.3lf",(By_Zephyr-ans)/1000.000);
	return 0;
}

2022/1/14 15:17
加载中...