网站制作方案策划简历,导航仪企业网站源码,建设网站的运行费包括什么地方,望城警务督察网站建设图片加载可能有点慢#xff0c;请跳过题面先看题解#xff0c;谢谢 很容易想到这样一个状态#xff1a;\(dp[l][r]\) 表示#xff0c;\(l\) 到 \(r\) 这一段区间#xff0c;双方都使用最优策略时#xff0c;先手能得到的最大分数 $ $ 那么这个只要怎么求呢#xff0c;想…图片加载可能有点慢请跳过题面先看题解谢谢 很容易想到这样一个状态\(dp[l][r]\) 表示\(l\) 到 \(r\) 这一段区间双方都使用最优策略时先手能得到的最大分数 $ $ 那么这个只要怎么求呢想一下\(dp[l][r]\) 要最大而 \(sum[l][r]\) 是固定的 所以 \(dp[l][r]sum[l][r]-min(min(dp[l][r]),min(dp[l][r]),0)\)其中 \(l1\le l\le r\)\(l\le r\le r-1\) 我们记 \(f[l][r]min(dp[l][r]),l\le l\le r\)\(g[l][r]min(dp[l][r]),l\le r\le r\) 显然有转移 \(dp[l][r]sum[l][r]-min(f[l1][r],g[l][r-1],0)\)\(f[l][r]min(dp[l][r],f[l1][r])\)\(g[l][r]min(dp[l][r],g[l][r-1])\)那么最后的答案就是\(2*dp[1][n]-sum[1][n]\) //made by Hero_of_Someone
#includeiostream
#includecstdio
#includecstdlib
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x0,q1; RG char chgetchar(); while( ( ch0 || ch9 ) ch!- ) chgetchar();if( ch- ) q-1,chgetchar(); while(ch0 ch9) xx*10ch-48,chgetchar(); return q*x; }int n,a[540],sum[540];
int f[540][540],g[540][540],dp[540][540];il void init(){for(RG int i1;in;i) a[i]gi(),sum[i]sum[i-1]a[i];for(RG int i1;in;i) f[i][i]g[i][i]dp[i][i]a[i];
}il void work(){for(RG int len1;lenn;len)for(RG int l1;llenn;l){RG int rllen,Min0;Minmin(Min,min(f[l1][r],g[l][r-1]));dp[l][r]sum[r]-sum[l-1]-Min;f[l][r]min(dp[l][r],f[l1][r]);g[l][r]min(dp[l][r],g[l][r-1]);}RG int ans(dp[1][n]1)-sum[n]; printf(%d\n,ans);
}int main(){ while(scanf(%d,n)n){ init(); work(); } return 0; }转载于:https://www.cnblogs.com/Hero-of-someone/p/7655387.html
