题目传送：UVA – 10891
思路：定义dp(i,j)表示原序列中的第i~j个元素组成的子序列，，在双方都采取最优策略的情况下，先手得分的最大值
通过枚举给对方剩下怎样的子序列，有
状态转移方程为：dp(i, j) = sum(i, j) – min{d(i+1, j), d(j, j) ,d(i,j-1),…,d(i,i),0};
AC代码①(On^3)：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;const int maxn = 105;int d[maxn][maxn];int vis[maxn][maxn], a[maxn]; int sum[maxn];int n;int dp(int i, int j) {if(vis[i][j]) return d[i][j];vis[i][j] = 1;int m = 0;for(int k = i; k < j; k ++) m = min(m, dp(i, k));for(int k = i + 1; k <= j; k ++) m = min(m, dp(k, j));d[i][j] = sum[j] – sum[i – 1] – m;return d[i][j];}int main() {while(scanf("%d", &n) != EOF) {if(n == 0) break;sum[0] = 0;for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);sum[i] = sum[i-1] + a[i];}memset(vis, 0, sizeof(vis));printf("%d\n", 2 * dp(1, n) – sum[n]);}return 0;}
AC代码②(On^2)：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;const int maxn = 105;int d[maxn][maxn];//记录先手在区间i到j中取得的最大值 int f[maxn][maxn];//记录min{d(i,j),d(i+1,j),…,d(j,j)},后缀 int g[maxn][maxn];//记录min{d(i,j),d(i,j-1),…,d(i,i)},前缀 int a[maxn];int sum[maxn];int n;int main() {while(scanf("%d", &n) != EOF) {if(n == 0) break;sum[0] = 0;for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);sum[i] = sum[i-1] + a[i];}for(int i = 1; i <= n; i ++) {f[i][i] = g[i][i] = d[i][i] = a[i];}for(int len = 1; len <= n; len ++) {for(int i = 1; i + len <= n; i ++) {int j = i + len;int m = 0;m = min(m, f[i + 1][j]);m = min(m, g[i][j – 1]);d[i][j] = sum[j] – sum[i – 1] – m;f[i][j] = min(d[i][j], f[i+1][j]);g[i][j] = min(d[i][j], g[i][j-1]);}}cout << 2 * d[1][n] – sum[n] << endl;}return 0;}
有一些喷着香水闻不到的空气，有一些在写字楼里永远遇不见的人。
