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

爱被打了一巴掌 2022-06-07 04:38 218阅读 0赞

有一个数轴，0-11，人站在5的位置，天上开始掉馅饼；  
人的移动速度为1，就是第一秒内只能接住4，5，6其中一个，给出馅饼掉落的位置和时间，问最多能得到多少个馅饼；  
我们知道起始位置，但是不知道末位置；  
用一个矩阵数组，二维数组dp来表示馅饼；  
dp\[i\]\[j\]，i代表出现的时间，j代表位置（为了好计算我们把位置全部加1，变为1-11）；  
我们不知道时间多长，记录最大时间，利用时间来计算最大数量；  
倒着遍历时间，然后遍历每一个位置  
dp\[i\]\[j\] i代表时间i，j代表j位置的时候接的最大数  
状态转移方乘为  
dp\[i\]\[j\] += max(dp\[i+1\]\[j\], max(dp\[i+1\]\[j-1\], dp\[i+1\]\[j+1\]));  
一个人需要可以接3个位置，所以需要判断3个，边界除外  
最后输出起点即可

#include<iostream>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    const int maxn = 99999 + 5;
    int dp[maxn][15];
    
    int main () {
        int n;
        while(cin >> n && n) {
            memset(dp, 0, sizeof dp);
            int a, b, t = 0;
            for(int i = 1; i <= n; i++) {
                scanf("%d %d", &a, &b);
                dp[b][a+1]++;
                t = max(t, b);
            }
            for(int i = t-1; i >= 0; i--) {
                for(int j = 11; j >= 1; j--) { //不能多 
                    dp[i][j] += max(dp[i+1][j], max(dp[i+1][j-1], dp[i+1][j+1]));
                }
            }   
            cout << dp[0][6] << endl;
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1176 免费馅饼（dp）

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

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

相关 HDU-1176免费馅饼

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

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

相关 hdu1176——免费馅饼

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1176][http_acm.hdu.edu.cn_showproblem.p

爱被打了一巴掌/ 2022年07月16日 08:44/ 0 赞/ 180 阅读

相关免费馅饼——动态规划

Think: 1状态转移方程：状态a\[i\]\[j\]表示在时刻i在位置j所能接到的最大馅饼数 a\[i\]\[0\] += max(a\[i+1\]\[0\]

落日映苍穹つ/ 2022年06月17日 03:52/ 0 赞/ 181 阅读

相关 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 赞/ 219 阅读

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

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

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

相关 HDU1176免费馅饼

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

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

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

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

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

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

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

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