软件库网站大全,win优化大师,装修黑榜第一名,wordpress 输出sql题意:经典的取石子游戏是这样的:有一堆石子#xff0c;A、B两个人轮流取#xff0c;每次取一颗#xff0c;只能从边上取#xff0c;每个石子有相应的价值#xff0c;A、B两人都想使得自己的价值最多#xff0c;两个人足够聪明#xff0c;问最后价值分别是多少 本题则是可…题意:经典的取石子游戏是这样的:有一堆石子A、B两个人轮流取每次取一颗只能从边上取每个石子有相应的价值A、B两人都想使得自己的价值最多两个人足够聪明问最后价值分别是多少 本题则是可以取多颗但仍然只能从一侧取得 分析状态转移方程 best[i][j]sum[i][j]-min(best[i][j-k],best[ik][j] 0);{1kj-i1}. 使用了记忆化的方法On3书上说有进一步的优化不过当前数据下已经很快了64ms 代码 View Code 1 #include stdio.h2 #include iostream3 #include string.h4 using namespace std;5 const int MAXN 100 10;6 #define DEBUG7 int min(int a, int b){8 return ab?a:b;9 }
10 int s[MAXN], a[MAXN], d[MAXN][MAXN], vis[MAXN][MAXN], n;
11 int dp(int i, int j){
12 if(vis[i][j]) return d[i][j];
13 vis[i][j]1;
14 int m0, k;
15 for(ki1; kj; k) mmin(m, dp(k, j));
16 for(ki; kj; k) mmin(m, dp(i, k));
17 d[i][j]s[j]-s[i-1]-m;;
18 return d[i][j];
19 }
20 int main(){
21 #ifndef DEBUG
22 freopen(in.txt, r, stdin);
23 #endif
24 while(scanf(%d, n)!EOF n){
25 s[0]0;
26 int i;
27 for(i1; in; i){
28 scanf(%d, a[i]);
29 s[i] s[i-1] a[i];
30 }
31 memset(vis, 0, sizeof(vis));
32 printf(%d\n, 2*dp(1,n)-s[n]);
33 }
34 return 0;
35 } 转载于:https://www.cnblogs.com/zjutzz/archive/2013/02/14/2911230.html
