Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1420
DP题，参照了之前的一道题：http://blog.csdn.net/Human_CK/archive/2011/02/17/6191860.aspx，理解后修改了几个地点，居然写出了第一道有点模样的DP，哈哈哈！
这道题不是左右轮流取，而是左或右取完一个后必须被另一个人去掉一个，而那个人取的时候会采取最有策略。
所以取左或取右之后得判断下一步被取完之后的最小值。
代码如下：
#include <iostream>using namespace std;int dp[105][105];int min(int a, int b){ if (a<=b) return a; else return b;}int search(int L, int R){ if (L>R) return 0; if (dp[L][R]!=-1) return dp[L][R]; int a = min(search(L+2, R), search(L+1, R-1)) + dp[L][L]; int b = min(search(L, R-2), search(L+1, R-1)) + dp[R][R]; dp[L][R] = a>=b?a:b; return dp[L][R];}int main(){ int n,i,j,sum; scanf("%d", &n); while(scanf("%d", &n)!=EOF) { for (i=1; i<=n; i++) for (j=1; j<=n; j++) dp[i][j] = -1; sum = 0; for (i=1; i<=n; i++) { scanf("%d", &dp[i][i]); sum += dp[i][i]; } n = search(1, n); printf("%d %d/n", n, sum-n); } return 0;}
