{"id":280,"date":"2010-06-12T14:41:00","date_gmt":"2010-06-12T06:41:00","guid":{"rendered":"http:\/\/localhost\/?p=280"},"modified":"2010-06-12T14:41:00","modified_gmt":"2010-06-12T06:41:00","slug":"jsoi2009_treasure_map_of_mars","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=280","title":{"rendered":"[JSOI2009]\u706b\u661f\u85cf\u5b9d\u56fe"},"content":{"rendered":"\n

[JSOI2009]\u706b\u661f\u85cf\u5b9d\u56fe<\/p>\n

Time Limit:5000MS Memory Limit:65536K
Total Submit:38 Accepted:17
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

<\/p>\n

Input <\/strong><\/p>\n

<\/p>\n

Output <\/strong><\/p>\n

<\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Hint <\/strong><\/p>\n

<\/p>\n

Source <\/strong><\/p>\n

JSOI2009Day2<\/p>\n

\u56e7\u554a\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u96be\u7684\u9898\u76ee\u3002\u3002\u9996\u5148\u80af\u5b9a\u662f\u8981DP\u7684\u3002\u4f46\u662f\u66b4\u529bDp\u662fN^2\u989d\u56e7\u3002\u3002
\u663e\u7136\u8981\u4f18\u5316\u3002\u3002\u600e\u4e48\u4f18\u5316\u5462\uff1fDp\u7684\u590d\u6742\u5ea6=\u72b6\u6001\u6570*\u6bcf\u4e2a\u72b6\u6001\u8ba1\u7b97\u9700\u8981\u7684\u65f6\u95f4\u3002\u3002\u3002
\u72b6\u6001\u6570\u80af\u5b9a\u53d8\u53d8\u4e0d\u4e86\uff0c\u662fN\u4e2a\u3002\u3002\u8003\u8651\u51cf\u5c11\u540e\u4e00\u9879\uff0c
\u4e5f\u5c31\u662f\u5f53\u524d\u9700\u8981\u8003\u8651\u7684\u8fc7\u53bb\u72b6\u6001\u4e2a\u6570\uff0c\u6ce8\u610f\u5230\u52a0\u5165A\u53ef\u4ee5\u5230\u8fbeB\uff0cB\u53ef\u4ee5\u5230\u8fbeC\u7684\u8bdd\uff0c
\u663e\u7136\u4e0d\u4f1a\u7528A\u6765\u66f4\u65b0C\u3002\u3002\u3002\u4ece\u4e0a\u5230\u4e0b\uff0c\u4ece\u5de6\u5230\u53f3\u8003\u8651\uff0c\u90a3\u4e48\u6bcf\u5217\u6700\u591a\u4e00\u4e2a\u662f\u6709\u7528\u7684\u3002\u3002
\u5c31\u53ef\u4ee5\u5f04\u51fa\u4e00\u4e2aNM\u7684\u7b97\u6cd5\u4e86\u3002\u3002\u3002
Code\uff1a<\/p>\n

#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 <\/p>\n","protected":false},"excerpt":{"rendered":"

[JSOI2009]\u706b\u661f\u85cf\u5b9d\u56fe Time Limit:5000MS Memory Limit:65536KTotal Submit:38 Accepted:17 Case Time Limit:1000MS Description Input Output Sample Input Sample Output Hint Source JSOI2009Day2 \u56e7\u554a\u3002\u3002\u770b\u4e0a\u53bb\u5f88\u96be\u7684\u9898\u76ee\u3002\u3002\u9996\u5148\u80af\u5b9a\u662f\u8981DP\u7684\u3002\u4f46\u662f\u66b4\u529bDp\u662fN^2\u989d\u56e7\u3002\u3002\u663e\u7136\u8981\u4f18\u5316\u3002\u3002\u600e\u4e48\u4f18\u5316\u5462\uff1fDp\u7684\u590d\u6742\u5ea6=\u72b6\u6001\u6570*\u6bcf\u4e2a\u72b6\u6001\u8ba1\u7b97\u9700\u8981\u7684\u65f6\u95f4\u3002\u3002\u3002\u72b6\u6001\u6570\u80af\u5b9a\u53d8\u53d8\u4e0d\u4e86\uff0c\u662fN\u4e2a\u3002\u3002\u8003\u8651\u51cf\u5c11\u540e\u4e00\u9879\uff0c\u4e5f\u5c31\u662f\u5f53\u524d\u9700\u8981\u8003\u8651\u7684\u8fc7\u53bb\u72b6\u6001\u4e2a\u6570\uff0c\u6ce8\u610f\u5230\u52a0\u5165A\u53ef\u4ee5\u5230\u8fbeB\uff0cB\u53ef\u4ee5\u5230\u8fbeC\u7684\u8bdd\uff0c\u663e\u7136\u4e0d\u4f1a\u7528A\u6765\u66f4\u65b0C\u3002\u3002\u3002\u4ece\u4e0a\u5230\u4e0b\uff0c\u4ece\u5de6\u5230\u53f3\u8003\u8651\uff0c\u90a3\u4e48\u6bcf\u5217\u6700\u591a\u4e00\u4e2a\u662f\u6709\u7528\u7684\u3002\u3002\u5c31\u53ef\u4ee5\u5f04\u51fa\u4e00\u4e2aNM\u7684\u7b97\u6cd5\u4e86\u3002\u3002\u3002Code\uff1a #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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/280"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=280"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/280\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}