{"id":42,"date":"2009-11-26T18:44:00","date_gmt":"2009-11-26T10:44:00","guid":{"rendered":"http:\/\/localhost\/?p=42"},"modified":"2009-11-26T18:44:00","modified_gmt":"2009-11-26T10:44:00","slug":"usaco_2005_november_gold","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=42","title":{"rendered":"USACO 2005 November Gold"},"content":{"rendered":"<p> @@@@1@@@@<br \/>\u6c34\u9898\u3002\u3002\u3002\u6bcf\u884c\u6bcf\u5217\u5efa\u4e2a\uff38\uff38\u7136\u540e\u4e8c\u5206\u56fe\u7136\u540e\u6700\u5c0f\u8986\u76d6\u96c6\u3002\u3002<br \/>\u592a\u6c34\u4e0d\u60f3\u5199\u3002\u3002<br \/>@@@@2@@@@<br \/>DP\u963f\u3002\u3002<br \/>\u52a0\u5165l\u4e4b\u540e\u3002\u3002<br \/>DP[1][l][r]\u76ee\u524d\u5728r\u3002\u3002\u6700\u5c0f\u7684\u603b\u4ee3\u4ef7\u3002\u3002<br \/>DP[0][l][r]\u76ee\u524d\u5728l\u3002\u3002\u6700\u5c0f\u7684\u603b\u4ee3\u4ef7\u3002\u3002<br \/>Ans=min(DP[0][0][n-1],DP[1][0][n-1])<br \/>#include&lt;iostream&gt;<br \/>#include&lt;algorithm&gt;<br \/>#include&lt;queue&gt;<br \/>using namespace std;<br \/>const int maxn=1000+10,inf=~0U&gt;&gt;1;<br \/>int P[maxn];<br \/>int DP[2][maxn][maxn];<br \/>bool inQ[2][maxn][maxn]={0};<br \/>struct node<br \/>{<br \/> int d,l,r;<br \/> node(int d,int l,int r):d(d),l(l),r(r){}<br \/>};<br \/>queue&lt;node&gt; Q;<br \/>inline void Push(int d,int l,int r)<br \/>{<br \/> inQ[d][l][r]=true;<br \/> Q.push(node(d,l,r));<br \/>}<br \/>inline void Renew(int d,int l,int r,int c)<br \/>{<br \/> if(DP[d][l][r]&gt;c)<br \/> {<br \/>  DP[d][l][r]=c;<br \/>  if(!inQ[d][l][r])<br \/>   Push(d,l,r);<br \/> }<br \/>}<br \/>int n,l;<br \/>int main()<br \/>{<br \/> cin&gt;&gt;n&gt;&gt;l;<br \/> for(int i=0;i&lt;n;i++) cin&gt;&gt;P[i];<br \/> P[n]=l;n++;<br \/> for(int d=0;d&lt;2;d++)<br \/>  for(int i=0;i&lt;n;i++)<br \/>   for(int j=0;j&lt;n;j++)<br \/>    DP[d][i][j]=inf;<br \/> sort(P,P+n);<br \/> int i=lower_bound(P,P+n,l)-P;<br \/> DP[0][i][i]=DP[1][i][i]=0;<br \/> Push(0,i,i);Push(1,i,i);<br \/> while(Q.size())<br \/> {<br \/>  int d,l,r;<br \/>  node c=Q.front();Q.pop();inQ[d=c.d][l=c.l][r=c.r]=false;<br \/>  int cost=DP[d][l][r],num=n-(r-l+1);<br \/>  if(c.d==0)<br \/>  {<br \/>   if(l) Renew(0,l-1,r,cost+num*(P[l]-P[l-1]));<br \/>   if(r&lt;n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[l]));<br \/>  }<br \/>  else<br \/>  {<br \/>   if(l) Renew(0,l-1,r,cost+num*(P[r]-P[l-1]));<br \/>   if(r&lt;n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[r]));<br \/>  }<br \/> }<br \/> cout&lt;&lt;min(DP[0][0][n-1],DP[1][0][n-1])&lt;&lt;endl;<br \/>}@@@3@@@<br \/>???\u600e\u4e48\u6ca1\u6587\u4ef6\u7684\u3002\u3002<br \/>\u96be\u9053\u8981\u4e8b\u5148\u641e\u5230\u7a0b\u5e8f\u91cc\u9762\u53bb\uff1f\u9760\u3002\u3002\uff22\uff33\u963f\u3002\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"<p>@@@@1@@@@\u6c34\u9898\u3002\u3002\u3002\u6bcf\u884c\u6bcf\u5217\u5efa\u4e2a\uff38\uff38\u7136\u540e\u4e8c\u5206\u56fe\u7136\u540e\u6700\u5c0f\u8986\u76d6\u96c6\u3002\u3002\u592a\u6c34\u4e0d\u60f3\u5199\u3002\u3002@@@@2@@@@DP\u963f\u3002\u3002\u52a0\u5165l\u4e4b\u540e\u3002\u3002DP[1][l][r]\u76ee\u524d\u5728r\u3002\u3002\u6700\u5c0f\u7684\u603b\u4ee3\u4ef7\u3002\u3002DP[0][l][r]\u76ee\u524d\u5728l\u3002\u3002\u6700\u5c0f\u7684\u603b\u4ee3\u4ef7\u3002\u3002Ans=min(DP[0][0][n-1],DP[1][0][n-1])#include&lt;iostream&gt;#include&lt;algorithm&gt;#include&lt;queue&gt;using namespace std;const int maxn=1000+10,inf=~0U&gt;&gt;1;int P[maxn];int DP[2][maxn][maxn];bool inQ[2][maxn][maxn]={0};struct node{ int d,l,r; node(int d,int l,int r):d(d),l(l),r(r){}};queue&lt;node&gt; Q;inline void Push(int d,int l,int r){ inQ[d][l][r]=true; Q.push(node(d,l,r));}inline void Renew(int d,int l,int r,int c){ if(DP[d][l][r]&gt;c) { DP[d][l][r]=c; if(!inQ[d][l][r]) Push(d,l,r); }}int n,l;int main(){ cin&gt;&gt;n&gt;&gt;l; for(int i=0;i&lt;n;i++) cin&gt;&gt;P[i]; P[n]=l;n++; for(int d=0;d&lt;2;d++) for(int i=0;i&lt;n;i++) for(int j=0;j&lt;n;j++) DP[d][i][j]=inf; sort(P,P+n); int i=lower_bound(P,P+n,l)-P; DP[0][i][i]=DP[1][i][i]=0; Push(0,i,i);Push(1,i,i); while(Q.size()) [&hellip;]<\/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\/42"}],"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=42"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/42\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=42"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=42"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}