火星藏宝图

Time Limit: 10 Sec Memory Limit: 64 MB

Description

img

Input

img

Output

img

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

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
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 500005;
const int INF = 2147483640;

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=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

int main()
{
    n = get();   m = get();
    for(int i=1; i<=n; i++)
        a[i].x = get(),  a[i].y = get(), a[i].z = get();
    sort(a+1, a+n+1, cmp);

    memset(f, -127, sizeof(f));
    pos[1] = 1; f[1] = 0;
    for(int id=1; id<=n; id++)
    {
        int x = a[id].x, y = a[id].y;
        int record = -INF;
        for(int j=1; 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]);
}