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

我就是我 2022-06-10 03:20 152阅读 0赞

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

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int Max(int a, int b, int c);
    
    int dp[101400][14];
    
    int main(){
        int n, x, t, m, i, j;
        while(scanf("%d", &n) && n){
            memset(dp, 0, sizeof(dp));
            m = 0;
            for(i = 0; i < n; i++){
                scanf("%d %d", &x, &t);
                dp[t][x]++;
                m = max(m, t);
            }
            for(i = m-1; i >= 0; i--){
                dp[i][0] += max(dp[i+1][0], dp[i+1][1]);
                for(j = 1; j <= 9; j++){
                    dp[i][j] += Max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]);
                }
                dp[i][10] += max(dp[i+1][9], dp[i+1][10]);
            }
            printf("%d\n", dp[0][5]);
        }
        return 0;
    }
    int Max(int a, int b, int c){
        int t1 = max(a, b);
        int t = max(t1, c);
        return t;
    }

[vjudge]: https://vjudge.net/contest/163018#problem/G

发表评论取消回复

表情：

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

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

相关阅读

相关 [kuangbin带你飞]专题十二基础DP1 G - 免费馅饼 HDU - 1176（数塔）

G - 免费馅饼 HDU - 1176 题目链接：[https://vjudge.net/contest/68966\problem/G][https_vjudg

川长思鸟来/ 2023年08月17日 15:41/ 0 赞/ 84 阅读

相关 HDU-1176免费馅饼

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

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

相关 hdu1176免费馅饼·（类数塔问题）

免费馅饼 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

àì夳堔傛蜴生んèń/ 2022年07月28日 09:52/ 0 赞/ 139 阅读

相关 hdu1176——免费馅饼

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

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

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

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

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

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

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

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

相关 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）

好长时间没有搞算法了，今天写道题练练手。免费馅饼 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 阅读