转:http://blog.csdn.net/iamzky/article/details/19993055
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2037
这篇国家论文写的很好:http://wenku.baidu.com/view/83d0a76925c52cc58bd6bea8
Code:
/* ID:zky OJ:BZOJ Index:2037 Language:C++ */ #include<cstdio> #include<cstring> #include<iomanip> #include<iostream> #include<algorithm> using namespace std; typedef long long lld; lld Abs(lld x){ return x<0?-x:x; } struct Egg{ lld x,y,v; bool operator<(const Egg &a)const{ return x<a.x; } }a[1001]; lld n,x0; lld f[1001][1001][2]; lld sum[1001]; int main(){ //freopen("egg.txt","r",stdin); cin>>n>>x0; for(lld i=1;i<=n;i++)cin>>a[i].x; for(lld i=1;i<=n;i++)cin>>a[i].y; for(lld i=1;i<=n;i++)cin>>a[i].v; //a[0].x=x0; sort(a+1,a+1+n); for(lld i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].v; memset(f,0xaf,sizeof(f)); for(lld i=1;i<=n;i++){ f[i][i][0]=f[i][i][1]=a[i].y-Abs(a[i].x-x0)*sum[n]; } //f[i][j][0]=i<-j //f[i][j][1]=i->j for(lld len=1;len<n;len++) for(lld i=1;i<=n;i++){ lld j=i+len; if(j>n)break; f[i][j][0]=a[i].y+max(f[i+1][j][0]-Abs(a[i].x-a[i+1].x)*(sum[n]-(sum[j]-sum[i])), f[i+1][j][1]-Abs(a[i].x - a[j].x)*(sum[n]-(sum[j]-sum[i]))); f[i][j][1]=a[j].y+max(f[i][j-1][0]-Abs(a[i].x-a[j].x)*(sum[n]-(sum[j-1]-sum[i-1])), f[i][j-1][1]-Abs(a[j].x-a[j-1].x)*(sum[n]-(sum[j-1]-sum[i-1]))); } cout<<fixed<<setprecision(3)<<max(f[1][n][0],f[1][n][1])/1000.0<<endl; return 0; }