题解 P4056 【[JSOI2009]火星藏宝图】

· · 题解

https://sakits.com/bzoj1560/

题解

　　这题网上题解大都是O(nm)的做法，实际上用斜率优化可以做到O(m^2)，可貌似只有lichangdongtw大爷提到了斜率优化，但是没细讲，那我就详细说一下吧...虽然会O(nm)肯定就会斜率优化了吧qaq

　　首先先说一下O(nm)的做法。设f(i)为走到第i个点时的最大收益，显然有：

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

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

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

　　所以对于每一列我们只需要保存可转移点中行数最大的点，从这些点转移就好了，那么转移复杂度是O(m)的，总复杂度O(nm)，可以卡过去。

　　观察一下方程，平方展开后有一些i和j的乘积，可以联想到斜率优化。这题如果使用斜率优化的话，可以桶排后做到O(m^2)，但是我们也可以改变一下状态表示，不需要桶排。

　　设f(i)(j)为走到(i,j)上的点的最大收益，枚举每一列最底下的点来转移，因为我们确定了转移点的列就能确定行，为了写方程更简单一些，我省略第一维来写方程，设pos_i为第i列上当前能转移的点的最大行数，x为当前点的行数：

dis_j=(x-pos_j)^2 f(i)=f(j)-dis_j-(i-j)^2+w_{x,i}

　　设j<k，且从k转移比从j转移优，则有：

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

　　然后就可以斜率优化了...注意横坐标相同时斜率要设为-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]);
}