HDU 1176(时间dp)

小鱼儿 2022-09-20 11:25 145阅读 0赞

题意：如题。

#include<iostream>
    using namespace std;
    
    int p[100000+10][11],dp[100000+10][11];
    
    int max(int a,int b,int c)
    {    int d;
         d=a>b ? a : b;
         return d > c ? d : c;
    }
    
    int max(int a,int b)
    {   return a>b ? a:b;
    }
    
    int main()
    {    int n,i,j,x,t,MaxT;
         while(scanf("%d",&n),n)
         {    MaxT=0;
              memset(dp,0,sizeof(dp));
              memset(p,0,sizeof(p));
              for(i=1;i<=n;i++)
              {   scanf("%d%d",&x,&t); MaxT=max(MaxT,t);
                  p[t][x]++;
              }
              dp[0][5]=0;
              int m=0;
              for(i=4;i<=6;i++)
              {   dp[1][i]=p[1][i];
                  m=max(m,dp[1][i]);
              }
             // dp[1][5]=m;
              for(i=2;i<=MaxT;i++)
              {   for(j=0;j<=10;j++)
                  {   if(j==0) dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+p[i][j];
          if(j>=1&&j<=9)     dp[i][j]=max(dp[i-1][j],dp[i-1][j+1],dp[i-1][j-1])+p[i][j];
          if(j==10) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+p[i][j];
                  }
             }
             int ans=0;
             for(i=0;i<=10;i++) ans=max(ans,dp[MaxT][i]);
             printf("%d\n",ans);
          }
    return 0;
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1176 免费馅饼（dp）

都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。

小鱼儿/ 2024年02月17日 19:13/ 0 赞/ 12 阅读

相关 HDU 1176(时间dp)

题意：如题。 include<iostream> using namespace std; int p[100000+10][11],

小鱼儿/ 2022年09月20日 11:25/ 0 赞/ 146 阅读

相关 hdu1176 dp

免费馅饼问题。分析：一道比较简单的dp问题，只要想到用dp\[i\]\[j\]去表示第i秒走到位置j所得到的最多馅饼数，这道题目也就解决了。状态转移方程是： dp

╰半夏微凉°/ 2022年08月20日 07:23/ 0 赞/ 225 阅读

相关 G - 免费馅饼 HDU - 1176 ——dp-金字塔

Think: 1知识点：dp 2题意分析：建立二维时间位置数组，然后从最后掉落时间开始，金字塔向上更新 3反思：注意不要数组越界，注意不同题目for循环更新方向不要

我就是我/ 2022年06月10日 03:20/ 0 赞/ 175 阅读

相关 HDU 1176 - 免费馅饼（动态规划 + DP）

有一个数轴，0-11，人站在5的位置，天上开始掉馅饼；人的移动速度为1，就是第一秒内只能接住4，5，6其中一个，给出馅饼掉落的位置和时间，问最多能得到多少个馅饼；我

爱被打了一巴掌/ 2022年06月07日 04:38/ 0 赞/ 223 阅读

相关 HDU - 1176 免费馅饼 (DP)

免费馅饼 Problem Description 都说天上不会掉馅饼，但有一

水深无声/ 2022年05月18日 10:16/ 0 赞/ 189 阅读

相关 HDU1176免费馅饼

这是一道简单的DP问题，所以可以较好地从这道题学习DP。首先，具有最优子结构的特征。第一秒需要对位置4、位置5和位置6进行选择，我们此时就需要知道通过相应的位置可以获得的

谁践踏了优雅/ 2022年05月16日 10:35/ 0 赞/ 196 阅读

相关 HDU-1176（基础方程DP）

Problem Description 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅

野性酷女/ 2021年12月22日 03:35/ 0 赞/ 186 阅读

相关 HDU —— 1176 免费馅饼的另一种解法（dp）

好长时间没有搞算法了，今天写道题练练手。免费馅饼 Time Limit: 2000/1000 MS (Java/Others) Memory Limit:

迈不过友情╰/ 2021年09月27日 05:54/ 0 赞/ 337 阅读

相关免费馅饼 HDU-1176【数塔+DP】题解

目录 1.题目 2.思路 3.代码 1.题目都说天上不会掉馅饼，但有一天gameb

╰半橙微兮°/ 2021年07月24日 14:56/ 0 赞/ 388 阅读