bzoj 2037: [Sdoi2008]Sue的小球

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 struct data

 {

     int x,y,v;

 }a[];

 int f[][][],n,x0,b[],sum[],tot;

 bool cmp(data a1,data a2)

 {

     return a1.x<a2.x;

 }

 int main()

 {

     scanf("%d%d",&n,&x0);

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

       {

         scanf("%d",&a[i].x);

         a[i].x-=x0;

       }

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

       {

         scanf("%d",&a[i].y);

         tot+=a[i].y;

       }

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

       scanf("%d",&a[i].v);

     sort(a,a+n+,cmp);

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

       b[i]=a[i].x;

     x0=lower_bound(b,b+n+,)-b;

     for(int i=x0-;i>=;i--)

       sum[i]=sum[i+]+a[i].v;

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

       sum[i]=sum[i-]+a[i].v;

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

       {

         f[x0][i][]=f[x0][i-][]+(sum[n]+sum[]-sum[i-])*abs(a[i].x-a[i-].x);

         f[x0][i][]=f[x0][i][]+(sum[n]+sum[]-sum[i])*abs(a[i].x);

       }

     for(int i=x0-;i>=;i--)

       {

         f[i][x0][]=f[i+][x0][]+(sum[n]+sum[]-sum[i+])*abs(a[i].x-a[i+].x);

         f[i][x0][]=f[i][x0][]+(sum[n]+sum[]-sum[i])*abs(a[i].x);

       }

     for(int i=x0-;i>=;i--)

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

         {

            f[i][j][]=f[i+][j][]+(sum[]-sum[i+]+sum[n]-sum[j])*abs(a[i].x-a[i+].x);

            f[i][j][]=min(f[i][j][],f[i+][j][]+(sum[]-sum[i+]+sum[n]-sum[j])*abs(a[i].x-a[j].x));

            f[i][j][]=f[i][j-][]+(sum[]-sum[i]+sum[n]-sum[j-])*abs(a[j].x-a[j-].x);

            f[i][j][]=min(f[i][j][],f[i][j-][]+(sum[]-sum[i]+sum[n]-sum[j-])*abs(a[j].x-a[i].x));

         }

     int x0=min(f[][n][],f[][n][]);

     printf("%.3lf\n",(tot-x0)*0.001);

     return ;

 }

很像以前在codevs上做的关路灯那个题，区间型DP，可知他不可能越过一盏灯去关另一盏。所以从起点开始，依次向两边扩展，f[i][j][0]表示关完区间[i,j]停在左边,[1]表示停在右边。

f[i][j][0]即可从f[i+1][j][0]转移来，又可从f[i+1][j][1]转移来。