BZOJ 2037 Sue的小球

发表于 | 更新于

Link

Solution

将最大收益转化成最小损失，在转移的时候将损失提前计算，这样DP即可。

Code

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int MAXN=1000+11;
const LL INF=1e15;
using std::sort;
using std::min;
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d){return min(min(a,b),min(c,d));}
struct poi{int x,y,v;}p[MAXN];
bool operator <(const poi &a,const poi &b){return a.x<b.x;}
int sumv[MAXN],mid,n;
LL f[MAXN][MAXN][2];
bool ud[MAXN][MAXN][2];
LL dist(int l,int r){return p[r].x-p[l].x;}
LL sigmaV(int l,int r){return sumv[r]-sumv[l-1];}
LL DP(int l,int r,int d)
{
	if(r<mid || l>mid) return INF;
	if(ud[l][r][d]) return f[l][r][d];
	LL &res=f[l][r][d];ud[l][r][d]=1;
	if(d==0)
		res=min(DP(l+1,r,0)+(sigmaV(1,l)+sigmaV(r+1,n))*dist(l,l+1),
				DP(l+1,r,1)+(sigmaV(1,l)+sigmaV(r+1,n))*dist(l,r));		
	else
		res=min(DP(l,r-1,1)+(sigmaV(1,l-1)+sigmaV(r,n))*dist(r-1,r),
				DP(l,r-1,0)+(sigmaV(1,l-1)+sigmaV(r,n))*dist(l,r));
	return res;
}
int main()
{
	int x0,sumy=0;get(n),get(x0);
	for(int i=1;i<=n;i++) get(p[i].x);
	for(int i=1;i<=n;i++) get(p[i].y);
	for(int i=1;i<=n;i++) get(p[i].v);
	p[++n].x=x0;p[n].y=0;p[n].v=0;
	sort(p+1,p+1+n);
	for(int i=1;i<=n;i++)
	{
		sumv[i]=sumv[i-1]+p[i].v;
		sumy+=p[i].y;
		if(p[i].x==x0 && p[i].y==0)
		{
			f[i][i][0]=f[i][i][1]=0;
			ud[i][i][0]=ud[i][i][1]=1;
			mid=i;
		}
	}
	printf("%.3lf\n",(sumy-min(DP(1,n,0),DP(1,n,1)))/1000.0);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */