调了一下午,求助
查看原帖
调了一下午,求助
335094
Lucifero楼主2020/12/26 17:20
#include<bits/stdc++.h>
using namespace std;
class PaintingEgg
{
public:
	int x,y,v;
}a[1001];
int sum[1001],f[1001][1001][2],N,x0,tall;
bool operator<(PaintingEgg l,PaintingEgg r){ return l.x<r.x; }
int Sum(int l,int r){ return sum[r]-sum[l-1]; }
void re_dp()
{
	int i;
	for(i=1;i<=N;i++) sum[i]=sum[i-1]+a[i].v;
	for(i=1;i<=N;i++)
		if (a[i].v==0 && a[i].x==x0)
			f[i][i][0]=f[i][i][1]=0;
}
int main()
{
	//【SDOI2008】Sue的小球
	int i,j,vv;
	scanf("%d%d",&N,&x0);
	memset(f,0x3f,sizeof(f));
	for(i=1;i<=N;i++) scanf("%d",&a[i].x);
	for(i=1;i<=N;i++)
	{
		scanf("%d",&a[i].y);
		tall+=a[i].y;
	}
	for(i=1;i<=N;i++) scanf("%d",&a[i].v);
	a[++N]=(PaintingEgg){x0,0,0};
	sort(a+1,a+N+1);
	re_dp();
	for(vv=1;vv<N;vv++)
		for(i=1,j=vv+i;i<=N && j<=N;i++,j=vv+i)
		{
			f[i][j][0]=min(f[i][j][0],f[i+1][j][0]-(Sum(1,i)+Sum(j+1,N))*(a[i+1].x-a[i].x));
			f[i][j][0]=min(f[i][j][0],f[i+1][j][1]-(Sum(1,i)+Sum(j+1,N))*(a[j].x-a[i].x));
			f[i][j][1]=min(f[i][j][1],f[i][j-1][0]-(Sum(1,i-1)+Sum(j,N))*(a[j].x-a[i].x));
			f[i][j][1]=min(f[i][j][1],f[i][j-1][1]-(Sum(1,i-1)+Sum(j,N))*(a[j].x-a[j-1].x));
		}
	printf("%.3lf",(tall-min(f[1][N][0],f[1][N][1]))/1000.0);
}
2020/12/26 17:20
加载中...