bzoj1560:[JSOI2009]火星藏宝图(贪心+DP+斜率优化)

Author Avatar
Sakits 3月 11, 2018

题解

  这题网上题解大都是O(nm)O(nm)的做法,实际上用斜率优化可以做到O(m2)O(m^2),可貌似只有lichangdongtw大爷提到了斜率优化,但是没细讲,那我就详细说一下吧…虽然会O(nm)O(nm)肯定就会斜率优化了吧qaq
  首先先说一下O(nm)O(nm)的做法。设f(i)f(i)为走到第ii个点时的最大收益,显然有:

f(i)=f(j)(xixj)2(yiyj)2+wif(i)=f(j)-(x_i-x_j)^2-(y_i-y_j)^2+w_i

  朴素的转移当然是O(n2)O(n^2)的,但是我们可以发现每一列上能转移的点行数大的一定比行数小的更优,因为:

(a+b)2>a2+b2(a+b)^2>a^2+b^2

  所以对于每一列我们只需要保存可转移点中行数最大的点,从这些点转移就好了,那么转移复杂度是O(m)O(m)的,总复杂度O(nm)O(nm),可以卡过去。
  观察一下方程,平方展开后有一些iijj的乘积,可以联想到斜率优化。这题如果使用斜率优化的话,可以桶排后做到O(m2)O(m^2),但是我们也可以改变一下状态表示,不需要桶排。
  设f(i)(j)f(i)(j)为走到(i,j)(i,j)上的点的最大收益,枚举每一列最底下的点来转移,因为我们确定了转移点的列就能确定行,为了写方程更简单一些,我省略第一维来写方程,设posipos_i为第ii列上当前能转移的点的最大行数,xx为当前点的行数:

disj=(xposj)2f(i)=f(j)disj(ij)2+wx,i\begin{gathered} dis_j=(x-pos_j)^2\\ f(i)=f(j)-dis_j-(i-j)^2+w_{x,i}\\ \end{gathered}

  设j<kj<k,且从kk转移比从jj转移优,则有:

f(j)disj+2ijj2<f(k)disk+2ikk2f(j)f(k)disj+diskj2+k2<2i(kj)f(j)f(k)disj+diskj2+k22(kj)<i\begin{gathered} f(j)-dis_j+2ij-j^2<f(k)-dis_k+2ik-k^2\\ f(j)-f(k)-dis_j+dis_k-j^2+k^2<2i(k-j)\\ \frac{f(j)-f(k)-dis_j+dis_k-j^2+k^2}{2(k-j)}<i\\ \end{gathered}

  然后就可以斜率优化了…注意横坐标相同时斜率要设为-inf

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010, inf=1e9;
const double eps=1e-6;
int n, m, x, y, z;
int f[maxn][maxn], w[maxn][maxn], pos[maxn], dis[maxn], q[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline double xl(int x, int y){return (x==y)?-inf:1.0*(f[pos[x]][x]-f[pos[y]][y]-dis[x]+dis[y]-x*x+y*y)/2/(y-x);}
int main()
{
	read(n); read(m);
	for(int i=1;i<=n;i++) read(x), read(y), read(w[x][y]);
	memset(f, 200, sizeof(f));
	f[1][1]=w[1][1]; pos[1]=1; w[1][1]=0; 
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++) dis[j]=(pos[j]!=0)*(pos[j]-i)*(pos[j]-i);
		int l=1, r=0;
		for(int j=1;j<=m;j++)
		{
			if(pos[j]) 
			{
				while(l<r && xl(q[r-1], q[r])>xl(q[r], j)-eps) r--;
				q[++r]=j; 
			}
			if(w[i][j])
			{
				while(l<r && xl(q[l], q[l+1])-eps<j) l++;
				f[i][j]=f[pos[q[l]]][q[l]]-dis[q[l]]-(q[l]-j)*(q[l]-j)+w[i][j];
				pos[j]=i; dis[j]=0;
				while(l<r && xl(q[r-1], q[r])>xl(q[r], j)-eps) r--;
				q[++r]=j; 
			}
		}
	}
	printf("%d\n", f[m][m]);
}