典型DP问题
问题描述:
给出一个有n个数序列a1,a2,a3...an,做一个博弈问题.
两人轮流重序列的两端取走一个数,在第二个人以最佳策略取数的情况下求第一个人取数的和的最大值.
问题分析:
两个人都以最佳策略取数,那么这个最佳策略就是一个一个最优解,考虑有n-2个数的序列,它的最优解为x,给这个序列再加上2个数,an-1,an,取这两个数的较大者加上x,就是一个新的最优解.反过来说,每个最优解,它减去序列中的一个数,都是另一种情况的最优解,所以最优子结构得证.
一个最优解可以加上数变成新的最优解,所以重叠子问题得证.可以用动态规划求解.
符号及变量说明:
记a为数的序列,ai为序列中第i个数.
记sum(i,j)为序列中第i个数到第j个数的和.
记f(i,j)为序列中由i开始到第j个数按照游戏规则能取得到的最大值.
模型的建立:
设得到一个子序列ai,ai+1,ai+2,...,aj-2,aj-1,aj;
由于后一个人按最佳策略取数,所以他必将取一个最大值f(i+1,j)或f(i,j-1),那么此时取数的人以后取得的数将是sum(i+1,j)-f(i+1,j)或是sum(i,j-1)-f(i,j-1),此时取数的人按最佳策略取数,他会取ai或者aj使得sum(i+1,j)-f(i+1,j)+ai和sum(i,j-1)-f(i,j-1)+aj二者能有较大值.这样从游戏的结束向游戏的开始推,可以得到总的最优解.
讲的甚是。都不知道有什么问题了。
就是这样.
代码:
/* ID:Andy Chen LANG:C++ TASK:game1 */ #include <iostream> #include <fstream> #include <algorithm> using namespace std; int a[101]={0}; int sum[101][101]={0}; //子段和 int max_sum[101][101]={0}; //记录各分段的最优 ifstream fin("game1.in"); ofstream fout("game1.out"); int main() { int N; int i,j,k; fin>>N; for(i=1;i<=N;i++) fin>>a[i]; for(int i=1;i<=N;i++) { sum[i][i]=max_sum[i][i]=a[i]; } for(i=1;i<=N;i++) for(j=i+1;j<=N;j++) //初始化子段和 { sum[i][j]=sum[i][j-1]+a[j]; } for(i=1;i<=N;i++) for(j=1;j<=N;j++) for(k=j+i;k<=N;k++) { max_sum[j][k]=max(a[j]+sum[j+1][k]-max_sum[j+1][k],a[k]+sum[j][k-1]-max_sum[j][k-1]); } fout<<max_sum[1][N]<<" "<<sum[1][N]-max_sum[1][N]<<endl; return 0; }
原文：http://www.cnblogs.com/cherry231/p/5196703.html