【BZOJ2037】Sue的小球（动态规划）

题面

BZOJ

题解

莫名想到这道题目

很明显是一样的

设\(f[i][j][0/1]\)表示已经接到了\(i～j\)这一段的小球

当前在\(i\)或者在\(j\)的最小费用

这个费用是随着时间增长，没有被接到的小球产生的

这样就可以避免存下时间

提前就把费用减去

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

double f[1010][1010][2];

struct Ege{double x,y,v;}a[1010];

int n;

double S[1010];

double tot;

bool operator<(Ege a,Ege b){return a.x<b.x;}

int main()

{

	n=read();double X=read();

	for(int i=1;i<=n;++i)a[i].x=read();

	for(int i=1;i<=n;++i)a[i].y=read();

	for(int i=1;i<=n;++i)a[i].v=read();

	sort(&a[1],&a[n+1]);

	for(int i=1;i<=n;++i)S[i]=S[i-1]+a[i].v;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			f[i][j][0]=f[i][j][1]=1e18;

	int l1=lower_bound(&a[1],&a[n+1],(Ege){X,0,0})-a;

	f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];l1--;

	f[l1][l1][0]=f[l1][l1][1]=1.0*abs(X-a[l1].x)*S[n];

	for(int len=2;len<=n;++len)

		for(int i=1;i<=n-len+1;i++)

		{

			int j=i+len-1;

			f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+1.0*(a[i+1].x-a[i].x)*(S[i]+S[n]-S[j]));

			f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+1.0*(a[j].x-a[i].x)*(S[i]+S[n]-S[j]));

			f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+1.0*(a[j].x-a[i].x)*(S[i-1]+S[n]-S[j-1]));

			f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+1.0*(a[j].x-a[j-1].x)*(S[i-1]+S[n]-S[j-1]));

		}

	for(int i=1;i<=n;++i)tot+=a[i].y;

	printf("%.3lf\n",(tot-min(f[1][n][0],f[1][n][1]))/1000.00);

	return 0;

}