oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

Asked by nsdy.wu on PKU2738

Posted on 2006-08-17 00:12 oyjpart 阅读(847) 评论(6)  编辑 收藏 引用

呵呵 居然有人问我题目啊~ 倍感荣幸!~
 这可是我人生中的第一次!~
不能辜负了人家的期望呀,拼命也要做做-_-|||
题目:
PKU 2738

Two Ends
Time Limit:1000MS  Memory Limit:65536K
Total Submit:605 Accepted:262

Description
In the two-player game "Two Ends", an even number of cards is laid out in a row. On each card, face up, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. Now one strategy is to simply pick the card at the end that is the largest -- we'll call this the greedy strategy. However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 3 instead of the 4.)
3 2 10 4
You are to determine exactly how bad the greedy strategy is for different games when the second player uses it but the first player is free to use any strategy she wishes.

Input
There will be multiple test cases. Each test case will be contained on one line. Each line will start with an even integer n followed by n positive integers. A value of n = 0 indicates end of input. You may assume that n is no more than 1000. Furthermore, you may assume that the sum of the numbers in the list does not exceed 1,000,000.

Output
For each test case you should print one line of output of the form:
In game m, the greedy strategy might lose by as many as p points.
where m is the number of the game (starting at game 1) and p is the maximum possible difference between the first player's score and second player's score when the second player uses the greedy strategy. When employing the greedy strategy, always take the larger end. If there is a tie, remove the left end.

Sample Input

4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0

Sample Output

In game 1, the greedy strategy might lose by as many as 7 points.
In game 2, the greedy strategy might lose by as many as 4 points.
In game 3, the greedy strategy might lose by as many as 5 points.

Source
East Central North America 2005

思维:
看到这题首先分析情形。初看似乎可以贪心(即每人2次的的一个回合内),偶WA了一次贪心。但是WA后,发现贪心出不了最优解(因为可能会有多组相同的解).
搜索显然不行 ,1000的长度 + multiple test case => absolutely TLE.
于是考虑DP.
是否满足最优子结构?恩。因为全局最优解包含局部最优解.
是否满足无后效性? 恩。当前所作决策可由当前状态唯一确定.
OK.DP.
首先是状态.不用说,用d[i][j]表示当前i->j的最大可能值(即2号选手少的分)
接着是状态转移.d[i][j]可能是两个方向转过来的,即选了最前面一个或最后面一个.然后2nd player也应该会有一个相应的选择.(具体见程序)
做好初始化的工作,就OK啦

Solution:

#include <stdio.h>
#include <string.h>
#include <math.h>

int a[1010], n, d[1010][1010];

int SecondDecision(int i, int j) //return which the Second player would like to get
{
if(a[i] >= a[j]) return i;
return j;
}

int Cal() //Dynamic Programming
{
int l, i, j, temp = 0;
for(i=1; i<n; i++)
d[i][i+1] = abs(a[i] - a[i+1]);
for(l = 4; l <= n; l += 2) //case length=2 has been calculated
for(i=1; i<=n-l+1; i++)
{
j = i+l-1;
if(SecondDecision(i+1, j) == j && d[i+1][j-1] >= 0)
{
temp = d[i+1][j-1] + a[i] - a[j];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
else if(d[i+2][j] >= 0)
{
temp = d[i+2][j] + a[i] - a[i+1];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}

if(SecondDecision(i, j-1) == j-1 && d[i][j-2] >= 0)
{
temp = d[i][j-2] + a[j] - a[j-1];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
else if(d[i+1][j-1] >= 0)
{
temp = d[i+1][j-1] + a[j] - a[i];
d[i][j] = temp > d[i][j] ? temp : d[i][j];
}
}
return d[1][n];
}

int main()
{
// freopen("ends.in", "r", stdin);
int i, ntc = 0;
while(scanf("%d", &n), n>0)
{
ntc++;
memset(a, 0, sizeof(a));
memset(d, -1, sizeof(d));
for(i=1; i<=n; i++)
scanf("%d", &a[i]);
printf("In game %d, the greedy strategy might lose by as many as %d points.\n", ntc, Cal());
}
return 0;
}
//代码写的不好 将就着看吧
呵呵 总算没辜负人家期望啊~ 好开心~

Feedback

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-17 03:48 by
强!~

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-17 12:04 by cainiao
thank you for your answer ~~~

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-17 15:50 by 踏雪赤兔
哈哈~~好心情,分享了

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-19 12:54 by 伟莉
竟是别有洞天!果真狡兔三窟。
遇上这样的程痴,自觉惭愧 -_-||
ANYWAY,加油!^^

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-27 10:37 by 路过
牛人!!!!!!!!

# re: Asked by nsdy.wu on PKU2738   回复  更多评论   

2006-08-27 10:38 by 路过
邮箱:zhangbin602@163.com

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理