2037: [Sdoi2008]Sue的小球

链接

题解

　　论文

代码

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 using namespace std;

 const int N = ;

 struct Node{

     int x,y,v;

     bool operator < (const Node &a) const {

         return x < a.x;

     }

 }d[N];

 int dp[N][N][],sum[N];

 inline int read() {

     int x = ,f = ;char ch=getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 int main() {

     int n = read(), x0 = read();

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

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

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

     sort(d+,d+n+);

     for (int i=; i<=n; ++i) sum[i] = sum[i-] + d[i].v; // 对下降速度求前缀和

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

         dp[i][i][] = dp[i][i][] = d[i].y - abs(x0-d[i].x)*sum[n]; //表示已经收集了[i,i]这个区间

     for (int k=; k<=n; ++k) {

         for (int i=; i+k-<=n; ++i) {

             int j = i + k - ;

             dp[i][j][] = max(dp[i+][j][] + d[i].y - (sum[n] - sum[j] + sum[i]) * (d[i+].x - d[i].x),

                               dp[i+][j][] + d[i].y - (sum[n] - sum[j] + sum[i]) * (d[j].x - d[i].x));

             dp[i][j][] = max(dp[i][j-][] + d[j].y - (sum[n] - sum[j-] + sum[i-]) * (d[j].x - d[i].x),

                               dp[i][j-][] + d[j].y - (sum[n] - sum[j-] + sum[i-]) * (d[j].x - d[j-].x));

         }

     }

     double ans = 1.0*(max(dp[][n][],dp[][n][]))/1000.0;

     printf("%.3lf",ans);

     return ;

 }