题目：有两个人A、B轮流在一串数字中取走一部分，每次只能从一侧取数，可以全取走但至少去一个，
A先取，问A最大能比B大多少，两个人都很聪明。
分析：动态规划（DP），区间DP。因为数字的总和是定值，所以差值最大就是A取走的数字的和最大。
状态定义：f（s，e）为在区间 [s, e] 上能取得的最大值；
转移方程：f（s，e）= max（sum（s，e），lmax（s，e），rmax（s，e））；
lmax = max（ sum（s，k）+ （sum（k+1，e）- f（k+1，e）））；
rmax= max（ （sum（s，k-1）- f（s，k-1））+ sum（k，e））；
说明：A在区间 [s, e] 上取走一部分是，B一定会取走剩下部分的最优解。
#include <stdio.h> #include <stdlib.h> int f[101][101]; int sum[101][101]; int data[101]; int main() { int n; while (~scanf("%d",&n) && n) { for (int i = 1; i <= n; ++ i) { scanf("%d",&data[i]); } for (int i = 1; i <= n; ++ i) { sum[i][i] = data[i]; for (int j = i+1; j <= n; ++ j) { sum[i][j] = sum[i][j-1] + data[j]; } } for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { f[i][j] = 0; } } //dp for (int l = 1; l <= n; ++ l) { for (int s = 1; s+l-1 <= n; ++ s) { int e = s+l-1; f[s][e] = sum[s][e]; for (int k = s; k < e; ++ k) { // left if (f[s][e] < sum[s][e] - f[k+1][e]) { f[s][e] = sum[s][e] - f[k+1][e]; } } for (int k = e; k > s; -- k) { // right if (f[s][e] < sum[s][e] - f[s][k-1]) { f[s][e] = sum[s][e] - f[s][k-1]; } } } } printf("%d\n",2*f[1][n]-sum[1][n]); } return 0; }