BZOJ2037 [Sdoi2008]Sue的小球

题面在这里

直接区间DP即可

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=1005;
int n,xx,X[maxn],s[maxn],f[maxn][maxn][2];
struct data{
int x,y,v;
bool operator<(const data&b)const {return x<b.x;}
}a[maxn];
#define w(l,r,t) ((s[(l)-1]+s[n]-s[r])*(t))
#define up(x,y) (x=max(x,y))
int main(){
scanf("%d%d",&n,&xx);
for (int i=1;i<=n;i++) scanf("%d",&a[i].x),X[i]=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);
n++;a[n].x=X[n]=xx;
sort(a+1,a+1+n);sort(X+1,X+1+n);
for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i].v;
cl(f,192);
{
for (int i=1;i<=n;i++)
if (a[i].x==xx) f[i][i][0]=f[i][i][1]=0;
}
for (int L=0;L<n;L++)
for (int i=1;i+L<=n;i++){
int j=i+L;
up(f[i-1][j][0],f[i][j][0]-w(i,j,X[i]-X[i-1])+a[i-1].y);
up(f[i-1][j][0],f[i][j][1]-w(i,j,X[j]-X[i-1])+a[i-1].y);
up(f[i][j+1][1],f[i][j][0]-w(i,j,X[j+1]-X[i])+a[j+1].y);
up(f[i][j+1][1],f[i][j][1]-w(i,j,X[j+1]-X[j])+a[j+1].y);
}
printf("%.3lf",max(f[1][n][0],f[1][n][1])/1000.0);
return 0;
}