考虑dp之后造成的影响
我们思考对于整体的影响，因为是区间dp我们分别统计就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
int n,x0,dp[N][N][2],sum[N];
struct Thing{
int x,y,v;
friend inline bool operator<(const Thing &A,const Thing &B){return A.x<B.x || (A.x==B.x && A.y<B.y);}
}a[N];
int Abs(int x){return x>0?x:-x;}
int main(){
freopen("2037.in","r",stdin);
freopen("2037.out","w",stdout);
scanf("%d %d",&n,&x0);
for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
for(int i=1;i<=n;i++)scanf("%d",&a[i].y);
for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].v;
for(int i=1;i<=n;i++)dp[i][i][0]=dp[i][i][1]=a[i].y-Abs(a[i].x-x0)*sum[n];
for(int len=1;len<n;len++){
for(int i=1;i<=n-len;i++){
dp[i][i+len][0]=max(dp[i+1][i+len][1]+a[i].y-(sum[n]-sum[i+len]+sum[i])*Abs(a[i].x-a[i+len].x),dp[i+1][i+len][0]+a[i].y-(sum[n]-sum[i+len]+sum[i])*Abs(a[i].x-a[i+1].x));
dp[i][i+len][1]=max(dp[i][i+len-1][1]+a[i+len].y-(sum[n]-sum[i+len-1]+sum[i-1])*Abs(a[i+len-1].x-a[i+len].x),dp[i][i+len-1][0]+a[i+len].y-(sum[n]-sum[i+len-1]+sum[i-1])*Abs(a[i].x-a[i+len].x));
}
}
printf("%.3lf\n",(double)(max(dp[1][n][0],dp[1][n][1])/1000.0));
return 0;
}
评论 (0)
