【BZOJ1560】【JSOI2009】火星藏宝图 [DP]

火星藏宝图

Time Limit: 10 Sec  Memory Limit: 64 MB
[Submit][Status][Discuss]

Description

　　

Input

　　

Output

　　

Sample Input

　　4 10
　　1 1 20
　　10 10 10
　　3 5 60
　　5 3 30

Sample Output

　　-4

HINT

　　1<= M <=2000, 2<= N <=100000.

Main idea

　　每个点上有一个收益，从一个点走到另外一个点的花费是欧几里得距离的平方，问从(1,1)走到(m,m)的最大收益。

Solution

　　首先，运用DP。而且若A < C < B，显然则有 (A-B)^2 > (A-C)^2 + (C-B)^2。

　　那么我们对横坐标排序一下，可以保证横向的大小关系。然后对于一个转移，每一纵向只有最接近它的点有用。这样就可以做到O(nm)了。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n,m;

 int pos[ONE];

 int f[ONE];

 struct power

 {

         int x,y,z;

 }a[ONE];

 bool cmp(const power &a, const power &b)

 {

         if(a.x != b.x) return a.x < b.x;

         return a.y < b.y;

 }

 int cost(int Ax, int Ay, int Bx, int By)

 {

         return (Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By);

 }

 int get()

 {

         int res=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 int main()

 {

         n = get();   m = get();

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

             a[i].x = get(),  a[i].y = get(), a[i].z = get();

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

         memset(f, -, sizeof(f));

         pos[] = ; f[] = ;

         for(int id=; id<=n; id++)

         {

             int x = a[id].x, y = a[id].y;

             int record = -INF;

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

             if(pos[j])

                 record = max( record, f[j] - cost(pos[j],j, x,y) );

             pos[y] = x;

             f[y] = record + a[id].z;

         }

         printf("%d", f[m]);

 }