hdu1176 dp

╰半夏微凉° 2022-08-20 07:23 172阅读 0赞

免费馅饼问题。

分析：

一道比较简单的dp问题，只要想到用dp\[i\]\[j\]去表示第i秒走到位置j所得到的最多馅饼数，这道题目也就解决了。

状态转移方程是：

dp\[i\]\[j\] += max(dp\[i+1\]\[j-1\],max(dp\[i+1\]\[j\],dp\[i+1\]\[j+1\]));

从最后一秒反向递推比较方便。

具体见代码：

//1176
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    int const maxn = 100005;
    int dp[maxn][12];
    //dp[i][j]表示的是第i秒站在位置j处共得到的馅饼数量
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF && n)
        {
            int num = -1;//最大的秒数
            memset(dp,0,sizeof(dp));
            for(int i = 0 ; i < n ; i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                if(y>num)num=y;
                dp[y][x+1]++;
                //位置变为1到11，这样处理边界好一点
            }
            for(int i = num ; i >= 0 ; i--)
            {
                for(int j = 1 ; j <= 11 ; j++)
                {
                    dp[i][j] += max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
                }
            }
            printf("%d\n",dp[0][6]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1176(时间dp)

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

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

相关 hdu1176 dp

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

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

相关 HDU-1176免费馅饼

</pre><pre name="code" class="cpp">//78ms include <cstring> inclu

桃扇骨/ 2022年08月11日 04:30/ 0 赞/ 139 阅读

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

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

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

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

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

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

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

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

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

相关 HDU1176免费馅饼

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

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

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

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

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

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

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

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

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

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

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