# re: 如何将动态规划解决不了的问题转化为判定性问题 回复 更多评论
2006-08-16 10:43 by
这位大哥..
偶是acm菜鸟...
你能给我讲讲pku 2738 的解题思路么..
email nsdy.wu@126.com
# re: 如何将动态规划解决不了的问题转化为判定性问题 回复 更多评论
2006-08-17 00:03 by
Nice to meet you here,
Very glad to share my ideas with you.
思维:
看到这题首先分析情形。初看似乎可以贪心，(偶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;
}
//代码写的不好 将就着看吧