6 5 1 4 1 6 1 7 2 7 2 8 3 0
4
數塔問題，自底向上分析，逐層遞推求解最終結果。
注意對0,10的特殊處理以及保證取最大時間的方法，時間並不一定按照順序寫出
核心代碼：
for(i=y-2;i>=0;i--)
{
for(j=1;j<10;j++)
dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]))+map[i][j];
dp[i][0]=max(dp[i+1][0],dp[i+1][1])+map[i][0];//注意這裡對0位置的特殊處理
dp[i][10]=max(dp[i+1][9],dp[i+1][10])+map[i][10];//對10位置的特殊處理
}測試數據：
6 5 3 7 2 9 1 8 1 4 12 7 5
3
#include#include #include using namespace std; int map[100000][11]; int dp[100000][11]; int solve(int y) { int i,j; for(i=0;i<11;i++) dp[y-1][i]=map[y-1][i]; for(i=y-2;i>=0;i--) { for(j=1;j<10;j++) dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]))+map[i][j]; dp[i][0]=max(dp[i+1][0],dp[i+1][1])+map[i][0];//注意這裡對0位置的特殊處理 dp[i][10]=max(dp[i+1][9],dp[i+1][10])+map[i][10];//對10位置的特殊處理 } return max(dp[0][4],max(dp[0][5],dp[0][6])); } int main() { int n,x,y,time; while(scanf("%d",&n)&&n) { time=0; memset(map,0,sizeof(map)); while(n--) { scanf("%d%d",&x,&y); map[y-1][x]+=1; time=max(time,y);//取得最大時間 } printf("%d\n",solve(time)); } return 0; }
