{"id":29,"date":"2009-11-14T22:56:00","date_gmt":"2009-11-14T14:56:00","guid":{"rendered":"http:\/\/localhost\/?p=29"},"modified":"2009-11-14T22:56:00","modified_gmt":"2009-11-14T14:56:00","slug":"spoj_5271","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=29","title":{"rendered":"SPOJ 5271"},"content":{"rendered":"<p> \u6c34\u9898\u3002\u3002\u76f4\u63a5\u66b4\u529bDP\u3002\u3002\u3002<br \/>dp(pos,last)\u8868\u793a\u5f53\u524d\u5728pos\u3002\u3002\u4e0a\u4e00\u6b21\u62ff\u4e86last\u3002\u6700\u591a\u80fd\u62ff\u591a\u5c11\u94b1\u3002\u3002<br \/>Code\u3002\u3002<br \/>#include&lt;iostream&gt;<br \/>#define REP(i,n) for(int i=0;i&lt;n;i++)<br \/>using namespace std;<br \/>const int maxn=2010,maxlast=1010;<br \/>int dp[maxn][maxlast]={0};<br \/>int C[maxn],n;<br \/>void init()<br \/>{<br \/> cin&gt;&gt;n;<br \/> REP(i,n) REP(j,n\/2+1)<br \/>  dp[i][j]=-1;<br \/> for(int i=0;i&lt;n;i++)<br \/> {<br \/>  cin&gt;&gt;C[i];<br \/>  C[i]+=i?C[i-1]:0;<br \/> }<br \/>}<br \/>int DP(int i,int last)<br \/>{ <br \/> int rest=C[n-1]-C[i-1];<br \/> last&lt;&lt;=1;<br \/> if(n-i-1&lt;=last)<br \/>  return rest;<br \/> if(dp[i][last]!=-1)<br \/>  return dp[i][last];<br \/> int get,ans=0;<br \/> for(int take=1;take&lt;=last;take++)<br \/> {<br \/>  get=rest-DP(i+take,take)+C[i+take]-C[i-1];<br \/>  ans=max(ans,get);<br \/> }<br \/> return dp[i][last]=ans;<br \/>}<br \/>int main()<br \/>{<br \/> init();<br \/> cout&lt;&lt;DP(0,1)&lt;&lt;endl;<br \/>}<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6c34\u9898\u3002\u3002\u76f4\u63a5\u66b4\u529bDP\u3002\u3002\u3002dp(pos,last)\u8868\u793a\u5f53\u524d\u5728pos\u3002\u3002\u4e0a\u4e00\u6b21\u62ff\u4e86last\u3002\u6700\u591a\u80fd\u62ff\u591a\u5c11\u94b1\u3002\u3002Code\u3002\u3002#include&lt;iostream&gt;#define REP(i,n) for(int i=0;i&lt;n;i++)using namespace std;const int maxn=2010,maxlast=1010;int dp[maxn][maxlast]={0};int C[maxn],n;void init(){ cin&gt;&gt;n; REP(i,n) REP(j,n\/2+1) dp[i][j]=-1; for(int i=0;i&lt;n;i++) { cin&gt;&gt;C[i]; C[i]+=i?C[i-1]:0; }}int DP(int i,int last){ int rest=C[n-1]-C[i-1]; last&lt;&lt;=1; if(n-i-1&lt;=last) return rest; if(dp[i][last]!=-1) return dp[i][last]; int get,ans=0; for(int take=1;take&lt;=last;take++) { get=rest-DP(i+take,take)+C[i+take]-C[i-1]; ans=max(ans,get); } return dp[i][last]=ans;}int main(){ init(); cout&lt;&lt;DP(0,1)&lt;&lt;endl;}<\/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\/29"}],"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=29"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}