UVA 12484:Cards（一头一尾取卡片）(动态规划,滚动数组)

Maratona de Programa??o da SBC – ACM ICPC – 2012 5
Problem C
Cards
Two players, Alberto and Wanderley, play a game. A set with an even number of cards, each card
containing an integer, is arranged on a table, one card next to another, forming a sequence of cards.
Alberto begins to play, and can take one of two cards at the edges of the sequence (the first or the last
card). Wanderley then can take one of two cards at the edges of the remaining sequence, and Alberto
can again take a card from the sequence, and so on, until Wanderley takes the last card.
In this game, the number of points of a player is the sum of the numbers in the cards he took.
Alberto, the first to play, aims to maximize his number of points. Wanderley, the second player, wants
to make Alberto to have the least number of points possible. In short, both want to do their best,
Alberto wanting to maximize his points and Wanderley wanting to minimize Alberto’s points.
You must write a program that, given the sequence of cards, determines the highest number of
points that Alberto can get.
Input
The input contains several test cases. Each test case is described in two lines. The first line contains
an integer N, which indicates the number of cards on the table. The second line contains N integers,
describing the sequence of cards.
Output
For each test case your program must print a single line, containing a single integer, the largest
number of points that Alberto can get.
Restrictions
? 2 <= N <= 10000
? N is even
? each of the N integers can be represented with 32 bits.
Example
Sample input
4
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7
Sample output
10
7
57

题意：两个人轮流取卡片，只能从首尾两端取，每个人取得所有卡片上的数值之和作为这一轮的得分，参与者要尽可能取得大数值并阻止对手取得大数值

转移方程 dp[i][j]=max(sum(i+1,j)-dp[i+1][j]+v[i],
sum(i,j-1)-dp[i][j-1]+v[j]);
面对第i个数和第j个数的序列要么取第i个元素要么取第j个元素
如果取了第i个数，接下来对方采取积极策略可以取到dp[i+1][j],
即去完第i个数后,剩下所有元素的和 —对手能取得的最大分数就是己方分数
取第j个数同理

二维dp数组写法

#include<bits/stdc++.h>
using namespace std;
const int MAX=10005;
int v[MAX];//存放卡牌的数值
int dp[MAX][MAX];
long long int sum[MAX];//sum[i]==v[0]到v[i]的累加和
//v[i]到v[j]的累加和==sum[j]-sum[i-1]  
int main(){
	int n; 
	while(cin>>n){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			cin>>v[i];
		} 
		sum[0]=0;
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1]+v[i];
		} 
//转移方程dp[i][j]代表面对第i个数和第j个数所能取到的最大分数
//	转移方程	dp[i][j]=max(sum(i+1,j)-dp[i+1][j]+v[i],
//							sum(i,j-1)-dp[i][j-1]+v[j]); 
// 面对第i个数和第j个数的序列要么取第i个元素要么取第j个元素 
//如果取了第i个数，接下来对方采取积极策略可以取到dp[i+1][j],
//即去完第i个数后,剩下所有元素的和 —对手能取得的最大分数 就是己方分数
// 取第j个数同理 
		int len0=2; 
		for(int i=1;i+len0-1<=n;i++){
			dp[2][i]=max(v[i],v[i+1]); 
		}
//初始化的写法还可以是
/*		int len0=1; //当然了这种写法就没有意义，len0=1的情况游戏是不允许的，完全是从dp数组的求值层面考虑，对了，这样初始化那就是从len=2开始求dp数组了
		for(int i=1;i+len0-1<=n;i++){
			dp[1][i]=v[i]; 
		}
*/
		for(int len=3;len<=n;len++){// len是讨论的这段数的长度，i是起始点 
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
				dp[len][i]=max(sum[j]-sum[i]-dp[len-1][i+1]+v[i],
				sum[j-1]-sum[i-1]-dp[len-1][i]+v[j]); 
//根据转移方程可以看出用到了上一行的正上方元素和右上角元素，
//只要得到上一行就ok，那么初始化就是对第一行啦 
			}
		}
		cout<<dp[n][1]<<endl;
	}
    return 0;
}

卡机过程

	//转移方程dp[i][j]代表面对第i个数和第j个数所能取到的最大分数
		for(int len=2;len<=n;len++){// len是讨论的这段数的长度，i是起始点 
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
//	转移方程	dp[i][j]=max(sum(i+1,j)-dp[i+1][j]+v[i],
//							sum(i,j-1)-dp[i][j-1]+v[j]); 
// 面对第i个数和第j个数的序列要么取第i个元素要么取第j个元素 
//如果取了第i个数，接下来对方采取积极策略可以取到dp[i+1][j],
//即去完第i个数后,剩下所有元素的和 —对手能取得的最大分数 就是己方分数
// 取第j个数同理 
	dp[i][j]=max(sum[j]-sum[i]-dp[i+1][j]+v[i],
				sum[j-1]-[i-1]-dp[i][j-1]+v[j]); 
//根据转移方程可以看出用到了下一行的正下方元素和同行前一个元素，
//看来需要从下往上求 ，那么初始化就是对第一行啦 。。。
//死机->重启
			} 
		}

两个一维数组的写法

#include<bits/stdc++.h>
using namespace std;
const int MAX=10005;
int v[MAX];//存放卡牌的数值
int cur[MAX];
int pre[MAX];//存放dp数组已经求好的上一行啦 
long long int sum[MAX];//sum[i]==v[0]到v[i]的累加和
//v[i]到v[j]的累加和==sum[j]-sum[i-1]  
int main(){
	int n; 
	while(cin>>n){
		memset(cur,0,sizeof(cur));
		memset(pre,0,sizeof(pre));
		for(int i=1;i<=n;i++){
			cin>>v[i];
		} 
		sum[0]=0;
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1]+v[i];
		} 
		
		for(int i=1;i<=MAX;i++){
			pre[i]=v[i]; 
		}
		for(int len=2;len<=n;len++){// len是讨论的这段数的长度，i是起始点 
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
				cur[i]=max(sum[j]-sum[i]-pre[i+1]+v[i],
				sum[j-1]-sum[i-1]-pre[i]+v[j]); 
			}
			for(int i=1;i+len-1<=n;i++){
				pre[i]=cur[i];	
			}
		}
		cout<<pre[1]<<endl;
	}
    return 0;
}

一维dp数组的写法

#include<bits/stdc++.h>
using namespace std;
const int MAX=10005;
int v[MAX];//存放卡牌的数值
int dp[MAX];
long long int sum[MAX];//sum[i]==v[0]到v[i]的累加和
//v[i]到v[j]的累加和==sum[j]-sum[i-1]  
int main(){
	int n; 
	while(cin>>n){
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			cin>>v[i];
		} 
		sum[0]=0;
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1]+v[i];
		} 
		
		for(int i=1;i<=MAX;i++){
			dp[i]=v[i]; 
		}
		for(int len=2;len<=n;len++){// len是讨论的这段数的长度，i是起始点 
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
	//dp数组只记录一行的情况，到了下一行时，在dp数组更新第i+1个元素之前
//	dp[i+1] 代表的就是上一行的 第i+1个元素
				dp[i]=max(sum[j]-sum[i]-dp[i+1]+v[i],
				sum[j-1]-sum[i-1]-dp[i]+v[j]); 
			}
		}
		cout<<dp[1]<<endl;
	}
    return 0;
}