BZOJ 1560 火星藏宝图(DP)

思路:发现如果从A能到B，B能到C，那么一定A能到C，且根据不等式:A^2+B^2<=(A+B）^2，而且权值没有负数，因此经过B比不经过B要优，因此，我们从左上到右下做，每一列，我们只记录之前做过的最下面的那个位置的信息，然后从这个位置的前几列里面寻找最优。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #define ll long long

 #define inf 999999999

 struct Point{

     int x,y,w;

     Point(){}

     Point(int x0,int y0):x(x0),y(y0){}

 }a[];

 int n,m,b[],c[];

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

     while (ch<=''&&ch>=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 bool cmp(Point p1,Point p2){

     if (p1.x!=p2.x) return p1.x<p2.x;

     return p1.y<p2.y;

 }

 int sqr(int x){

     return x*x;

 }

 int dis(Point p1,Point p2){

     return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);

 }

 int main(){

     n=read();m=read();

     for (int i=;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].w=read();

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

     for (int i=;i<=m;i++) b[i]=-inf;

     b[]=a[].w;

     c[]=;

     int tmp;

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

         int x=a[i].x,y=a[i].y,w=a[i].w;

         tmp=-inf;

         for (int j=;j<=y;j++)

          tmp=std::max(tmp,b[j]-dis(Point(x,y),Point(c[j],j)));

         tmp+=w;

         b[y]=tmp;c[y]=x;

     }

     printf("%d\n",tmp);

 }