# re: 如何將動(dòng)態(tài)規(guī)劃解決不了的問題轉(zhuǎn)化為判定性問題 回復(fù) 更多評(píng)論
2006-08-16 10:43 by
這位大哥..
偶是acm菜鳥...
你能給我講講pku 2738 的解題思路么..
email nsdy.wu@126.com
# re: 如何將動(dòng)態(tài)規(guī)劃解決不了的問題轉(zhuǎn)化為判定性問題 回復(fù) 更多評(píng)論
2006-08-17 00:03 by
Nice to meet you here,
Very glad to share my ideas with you.
思維:
看到這題首先分析情形。初看似乎可以貪心，(偶WA了一次貪心).但是WA后，發(fā)現(xiàn)貪心出不了最優(yōu)解（因?yàn)榭赡軙?huì)有多組相同的解).
搜索顯然不行 ,1000的長(zhǎng)度 + multiple test case => absolutely TLE.
于是考慮DP.
是否滿足最優(yōu)子結(jié)構(gòu)？恩。因?yàn)槿肿顑?yōu)解包含局部最優(yōu)解.
是否滿足無后效性? 恩。當(dāng)前所作決策可由當(dāng)前狀態(tài)唯一確定.
OK.DP.
首先是狀態(tài).不用說，用d[i][j]表示當(dāng)前i->j的最大可能值(即2號(hào)選手少的分）
接著是狀態(tài)轉(zhuǎn)移.d[i][j]可能是兩個(gè)方向轉(zhuǎn)過來的，即選了最前面一個(gè)或最后面一個(gè).然后2nd player也應(yīng)該會(huì)有一個(gè)相應(yīng)的選擇.(具體見程序)
做好初始化的工作,就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;
}
//代碼寫的不好 將就著看吧