首页 > 代码库 > HDU 1176 免费馅饼

HDU 1176 免费馅饼

2024-07-15 23:36:56   222人阅读

这题一开始没想到数塔,嘻嘻;由于是学校DIY里面的题目,所以百度了一下题目,拿到了题目测试数据,用来给freopen用的;

不小心瞄到数塔..不过再想想应该也是可以想到的..分析一下就懂了..

值得一提的是自己被题目骗了..最后一个输入的不一定是最大的时间..耽搁了一会- -找了半天原因嘞;//还有需要记得一点的是:正面不好做可以逆着做,像Super jumping 这类的.

读入数据的时候将每个位置+1,为了统一方法;               //把a数组去掉可以将时间从93ms下调至46MS;

下面给出代码:

 1 #include<iostream> 2 #define maxn 100010 3 int n,a[13][maxn],dp[13][maxn];//位置,时间 4 using namespace std; 5 int max(int a,int b,int c) 6 { 7     int d=a>b?a:b; 8     return c>d?c:d ; 9 }10 int main()11 {12     //freopen("1176.txt","r",stdin);13     int i,j;14     while(~scanf("%d",&n),n)15     {16         memset(a,0,sizeof(a));17         memset(dp,0,sizeof(dp));18         int i,j,b=0,t,x;19         for(i=1;i<=n;i++)20         {21             scanf("%d%d",&x,&t);22             a[x+1][t]+=1;23             if(b<t)  b=t;   24         }25         for(i=0;i<12;i++)26             for(j=0;j<maxn;j++)27               dp[i][j]=a[i][j];            28          for(i=b-1;i>=0;i--)29              for(j=1;j<12;j++)30                  dp[j][i]+=max(dp[j-1][i+1],dp[j][i+1],dp[j+1][i+1]);31     32              printf("%d\n",dp[6][0]);33          34     }35     return 0;36 }

 


联系
我们