hdu1176 免费馅饼
简单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; }
补充:软件开发 , C++ ,