Basketball Exercise（CF） ———— 简单dp

╰+哭是因爲堅強的太久メ 2024-04-17 20:46 60阅读 0赞

[题目连接][Link 1]

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn = 1e5+50;
    ll dp[2][maxn];
    ll a[2][maxn];
    ll n;
    void input(ll m)
    { 
        for(ll i = 0;i <= 1;i++)
        { 
            for(ll j = 1;j <= m;j++)cin>>a[i][j];
        }
    }
    int main()
    { 
    
    // cout <<sizeof(a)+sizeof(dp)<<endl;
        ios_base::sync_with_stdio(false);
        ll ans = 0;
        cin>>n;
        input(n);
    
        dp[0][n] = a[0][n];
        dp[1][n] = a[1][n];
        ans = max(ans, max(dp[0][n], dp[1][n]));
        for(ll i = n-1;i >= 1;i--)
        { 
            if(i+2 <= n)
            { 
                dp[0][i]+=max(dp[1][i+1],dp[1][i+2])+a[0][i];
                ans = max(ans, dp[0][i]);
                dp[1][i]+= max(dp[0][i+1], dp[0][i+2])+a[1][i];
                ans = max(ans, dp[1][i]);
            }
            else
            { 
                dp[0][i] +=dp[1][i+1]+a[0][i];
                ans = max(dp[0][i+1], ans);
                dp[1][i]+=dp[0][i+1]+a[1][i];
                ans = max(ans, dp[1][i]);
            }
    
        }
        cout <<ans<<endl;
    
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/1195/C

发表评论取消回复

表情：

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

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

相关阅读

相关 Leetcode 62. 不同路径（简单DP）

题目重述一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在

柔情只为你懂/ 2022年09月03日 13:14/ 0 赞/ 169 阅读

相关简单dp 最大连续子序列

//设n个元素的序列存储在数组A[1...n]中，求数组中连续子序列之和的最大值。 include <iostream> include <c

妖狐艹你老母/ 2022年08月18日 01:00/ 0 赞/ 194 阅读

相关 UVALive 4811 Growing Strings【AC自动机+简单dp】

AC自动机给出n个字符串，问最多能够选出多少个串组成序列，并满足前一个字符串是后一个字符串的子串。这个和上一题类似，但是更加简单。对于AC自动机，我们知道的是

男娘i/ 2022年08月08日 19:38/ 0 赞/ 67 阅读

相关简单dp的网站解释

http://blog.csdn.net/fofu33/article/details/8742078 http://blog.csdn.net/lyy289065406/a

我不是女神ヾ/ 2022年07月15日 12:27/ 0 赞/ 183 阅读

相关简单暴力到dp的优化（入门篇）

上篇，我们提到，遇到问题，首先根据定义写出笨方法，找出依赖关系（有些题这一步就不太简单，要自己归纳关系），然后进行优化，下面，我们通过几道此方面的经典的，较为简单的二维题目进行

淡淡的烟草味﹌/ 2022年05月27日 09:55/ 0 赞/ 145 阅读

相关简单暴力到dp的优化（萌新篇）

想写一系列文章，总结一些题目，看看解决问题、优化方法的过程到底是什么样子的。系列问题一：斐波那契数列问题在数学上，斐波纳契数列以如下被以[递归][Link 1]的方

小灰灰/ 2022年05月26日 21:05/ 0 赞/ 158 阅读

相关简单暴力到dp的优化(初级篇）

一、一维非脑残 1 一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串

左手的ㄟ右手/ 2022年05月25日 02:06/ 0 赞/ 108 阅读

相关简单暴力到dp的优化(中级篇）

下面再放三道我比较喜欢的，需要好好写一下的题。第一题比较水 1. White Cloud is exercising in the playground. White C

女爷i/ 2022年05月18日 05:48/ 0 赞/ 122 阅读

相关 hdoj最大连续子序列（简单dp）

最大连续子序列 Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Othe

约定不等于承诺〃/ 2022年04月01日 14:17/ 0 赞/ 217 阅读

相关（简单dp）hdu1466 计算直线的交点数

题目链接：[（简单dp）hdu1466 计算直线的交点数][dp_hdu1466] Problem Description 平面上有n条直线，且无三线共点，问这些直线能有多

冷不防/ 2022年03月10日 03:56/ 0 赞/ 205 阅读