37pts WA求助
查看原帖
37pts WA求助
419144
luckydrawbox楼主2022/8/23 19:46
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
	long long x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=1010,M=2e4+10;
int n,c;
ll dp[N][N][2],sp[M],ans;
struct asdf{
	int x;
	ll y,v; 
}a[N];
ll other(int l,int r){
	return sp[20000]-sp[a[r].x+10000]+sp[a[l].x+10000];
}
bool cmp(asdf p,asdf q){
	return p.x<q.x;
}
int main(){
	n=read();c=read();
	for(int i=1;i<=n;i++){
		a[i].x=read();
	}
	for(int i=1;i<=n;i++){
		a[i].y=read();
		ans+=a[i].y;
	}
	for(int i=1;i<=n;i++){
		a[i].v=read();
		sp[a[i].x+10000]+=a[i].v;
	}
	n++;
	a[n].x=c;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(!a[i].v&&a[i].x==c){
			c=i;
			break;
		}
	}
	for(int i=1;i<=20001;i++)
		sp[i]+=sp[i-1];
	memset(dp,0x3f,sizeof(dp));
	dp[c][c][0]=dp[c][c][1]=0;
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			dp[l][r][0]=min(dp[l+1][r][0]+other(l,r)*(a[l+1].x-a[l].x)
			,dp[l+1][r][1]+other(l,r)*(a[r].x-a[l].x));
			dp[l][r][1]=min(dp[l][r-1][1]+other(l-1,r-1)*(a[r].x-a[r-1].x)
			,dp[l][r-1][0]+other(l-1,r-1)*(a[r].x-a[l].x));
		}
	}
	printf("%.3lf\n",1.0*(ans-min(dp[1][n][0],dp[1][n][1]))/1000.0);
	return 0;
}
/*
3 0
-1 -1 1
0 0 0
1 2 5

*/
2022/8/23 19:46
加载中...