Posted on 2010-08-05 14:02
MiYu 閱讀(718)
評論(0) 編輯 收藏 引用 所屬分類:
C/C++ 、
ACM ( DP )
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1176
題目描述:
都說天上不會(huì)掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實(shí)在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲，雖然在游戲中是個(gè)身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍，每秒種只有在移動(dòng)不超過一米的范圍內(nèi)接住墜落的餡餅。現(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo).
為了使問題簡化，假設(shè)在接下來的一段時(shí)間里，餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置，因此在第一秒，他只能接到4,5,6這三個(gè)位置中期中一個(gè)位置上的餡餅。問gameboy最多可能接到多少個(gè)餡餅？（假設(shè)他的背包可以容納無窮多個(gè)餡餅）
很簡單的一道 DP 題目, 初看起來似乎很難, 但是自習(xí)分析,會(huì)發(fā)現(xiàn) , 這其實(shí)就是
數(shù)塔
的一道變形題!!!!
狀態(tài)轉(zhuǎn)移方程 :
pea[i-1][j] = pea[i-1][j] + max ( pea[i][j-1], pea[i][j] , pea[i][j+1] ) ;
下面照例是貼代碼 :
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
using std::max;
const int MAX_NUM = 100002;
int pea[MAX_NUM][11];
void setZero ( int t )
{
for ( int i = 0; i <= t; ++i )
{
for ( int j = 0; j != 11; ++ j )
{
pea[i][j] = 0;
}
}
}
int main ()
{
int N,temp = MAX_NUM;
while ( scanf ("%d",&N), N != 0 )
{
setZero ( temp );
int pos,sec;
int maxSec = 0;
for ( int i = 0; i != N; ++i )
{
scanf ( "%d%d",&pos,&sec ) ;
pea[sec][pos] ++ ;
if ( maxSec < sec )
{
maxSec = sec;
}
}
temp = maxSec;
for ( int i = maxSec; i != 0 ; -- i )
{
for ( int j = 0; j != 11; ++ j )
{
if ( j == 0 )
{
pea[i-1][j] += max ( pea[i][0] , pea[i][1] );
}
else if ( j == 10 )
{
pea[i-1][j] += max ( pea[i][9], pea[i][10] );
}
else
{
pea[i-1][j] += max ( max ( pea[i][j-1], pea[i][j] ), pea[i][j+1] );
}
}
}
printf ( "%d\n",pea[0][5] );
}
return 0;
}