簡單dp
題目要求:求dp[0][5]到dp[t][]的最大值
類似數塔 只不過1~9號位有三個方向可以選 0和10只有兩個
可將所有的時間段和餡餅看成是一個矩陣,時間就是行數,掉餡餅的就是列數,則就是數字三角形問題,從最底層找一條路徑,使得路徑上的和最大。
dp[i][j] 表示 i 時刻 j位置的最大值
開始搞不懂為什麼要for t->0 for 1->10 然後就得到dp[0][5]
首先要從最後一秒往前推 就像數塔從最下層開始往上算
然後算每一個位置能得到的最大值 因為你也不知道這些位置的下一個位置是不是終點 所以每一個位置從0->t都要算
#include<iostream> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; int dp[100005][15],n,t; int max3(int a,int b,int c) { int m=0; if(a>m) m=a; if(b>m) m=b; if(c>m) m=c; return m; } int main() { int i,j,a,b; while(scanf("%d",&n)&&n) { memset(dp,0,sizeof dp); t=0; while(n--) { scanf("%d%d",&a,&b); dp[b][a]++; t=max(t,b); } for(i=t;i>0;i--)//從最後一秒開始往前推 { for(j=0;j<=10;j++)//每一秒算以j為終點的最大值 { if(j==0)//j=0 或10 只有兩個方向選 { dp[i-1][j]+=max(dp[i][j],dp[i][j+1]); } else if(j==10) { dp[i-1][j]+=max(dp[i][j],dp[i][j-1]); } else { dp[i-1][j]+=max3(dp[i][j],dp[i][j-1],dp[i][j+1]); } } } printf("%d\n",dp[0][5]); } return 0; }