[JSOI2009]火星藏宝图

Time Limit:5000MS Memory Limit:65536K
Total Submit:38 Accepted:17
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Hint

Source

JSOI2009Day2

囧啊。。看上去很难的题目。。首先肯定是要DP的。但是暴力Dp是N^2额囧。。
显然要优化。。怎么优化呢？Dp的复杂度=状态数*每个状态计算需要的时间。。。
状态数肯定变变不了，是N个。。考虑减少后一项，
也就是当前需要考虑的过去状态个数，注意到加入A可以到达B，B可以到达C的话，
显然不会用A来更新C。。。从上到下，从左到右考虑，那么每列最多一个是有用的。。
就可以弄出一个NM的算法了。。。
Code：

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=1000,maxm=200000,inf=~0U>>2;int M[maxn],X[maxn]={},n,m;struct Land{ int i,j,v; Land(){} Land(int _i,int _j,int _v):i(_i),j(_j),v(_v){} bool operator<(const Land&o)const { if(i!=o.i)return i<o.i; return j<o.j; }}A[maxm];inline int Dist(int a,int b,int i,int j){ return (a-i)*(a-i)+(b-j)*(b-j);}int main(){ //freopen("in","r",stdin); scanf("%d%d",&n,&m);int x,y,v; rep(i,m)M[i]=-inf; rep(i,n) { scanf("%d%d%d",&x,&y,&v);–x;–y; A[i]=Land(x,y,v); } sort(A,A+n);int ret; M[0]=A[0].v; for(int i=1;i<n;i++) { x=A[i].i;y=A[i].j;v=A[i].v; ret=-inf; rep(j,y+1) ret>?=M[j]-Dist(x,y,X[j],j); ret+=v; M[y]=ret;X[y]=x; } printf("%dn",ret);}-44 101 1 2010 10 103 5 605 3 30