116
HDU1176-免費餡餅
免費餡餅Time Limit: 2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others)
Total Submission(s): 24187 Accepted Submission(s): 8162
Problem Description
都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉
下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉
，就掉落在他身旁的10米範圍內。餡餅如果掉在了地上當然就不能吃了，所
以gameboy馬上卸下身上的背包去接。但由於小徑兩側都不能站人，所以他
隻能在小徑上接。由於gameboy平時老呆在房間裏玩遊戲，雖然在遊戲中是
個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種隻有在移動不超
過一米的範圍內接住墜落的餡餅。現在給這條小徑如圖標上坐標：
置。開始時gameboy站在5這個位置，因此在第一秒，他隻能接到4,5,6這三
個位置中其中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（
假設他的背包可以容納無窮多個餡餅）
Input
輸入數據有多組。每組數據的第一行為以正整數n(0<n<100000)，表示有n個
餡餅掉在這條小徑上。在結下來的n行中，每行有兩個整數x,T
(0<T<100000),表示在第T秒有一個餡餅掉在x點上。同一秒鍾在同一點上可
能掉下多個餡餅。n=0時輸入結束。
Output
每一組輸入數據對應一行輸出。輸出一個整數m，表示gameboy最多可能接到m個餡餅。
提示：本題的輸入數據量比較大，建議用scanf讀入，用cin可能會超時。
Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4
動態規劃
AC代碼：
#include<stdio.h>
#include<string.h>
#define MAX 100010
int dp[MAX][11];//一開始存在第i秒落在j位置的餅有幾個，後期的意思是在有限秒內以該位置為起始點能拿到的最多餅
int max(int a,int b)
{return a>b?a:b;}
int main()
{
int i,n,x,y,Max_time,t,p;
while(scanf("%d",&n),n!=0)
{
memset(dp,0,sizeof(dp));
Max_time=0;//用來幾錄輸入的最大時間
for(i=0;i<n;i++)
{
scanf("%d %d",&x,&y);
dp[y][x]+=1;//在此秒內有幾個餅落在該坐標
if(y>Max_time)//更新最大時間
Max_time=y;
}
for(t=Max_time-1;t>=0;t--)//Max_time-1是為了防止後麵的t+1
溢出
{
for(p=0;p<=10;p++)
{
if(p==0)//如果在1處站著（0是哨兵位置）此時隻能往右走或者是停在原地，取最大值方案
dp[t][p]+=max(dp[t+1][p+1],dp[t+1][p]);
else if(p==10)//如果在10處站著，此時隻能往左走或者是停在原地，取最大值方案
dp[t][p]+=max(dp[t+1][p-1],dp[t+1][p]);
else//如果在1-10內站著，此時能往左走或者往右走或是停在原地，取最大值方案
dp[t][p]+=max(max(dp[t+1][p-1],dp[t+1][p]),dp[t
+1][p+1]);
}
}
//輸出以5為起始點，在Max_time時間內能拿到的最大餡餅數
printf("%d\n",dp[0][5]);
}
return 0;
}
最後更新：2017-04-03 08:26:14