Coin-row problem

青旅半醒 2022-05-26 12:19 150阅读 0赞

There is a row of n coins whose values are some positive integers c₁, c₂,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.

#### 输入 ####

Two lines, the first line is n (0< n <=10000), and the second line is value of coin(0< value <= 2^32).

#### 输出 ####

the maximum amount of money.

#### 样例输入 ####

6
    5 1 2 10 6 2

#### 样例输出 ####

17

思路：估计这老师才讲了dp 算法吧,这组题几乎全是dp（也是醉了）  
不能够相邻那么就考虑当前位的前两个数对应的最好状态+当前数，和当前数的前一个数的状态比较，这里的边界dp\[0\]=0,dp\[1\]=x\[1\](x数据元素数组从1开始存贮)，  
那么可以得到如下dp方程  dp\[i\] = max(dp\[i - 1\], dp\[i - 2\] + x\[i\]);

#include <iostream>  
        using namespace std;  
        int n, dp[10001], i, x[10001];  
        #define max(a,b) a>b?a:b  
        int main()  
        {  
            cin >> n;  
            for (i = 1; i <= n; i++) cin >> x[i];  
            dp[1] = x[1];  
            for (i = 2; i <= n; i++)  
                dp[i] = max(dp[i - 1], dp[i - 2] + x[i]);  
            cout << dp[n] << "\r\n";  
            return 0;  
        }

发表评论取消回复

表情：

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

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

相关阅读

相关 Daily Coding Problem: Problem #315

/ This problem was asked by Google. In linear algebra, a Toeplitz

秒速五厘米/ 2023年06月01日 12:53/ 0 赞/ 12 阅读

相关 Sum Problem

Sum Problem Time Limit: 500ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述 Hey, welcom

客官°小女子只卖身不卖艺/ 2022年08月10日 03:43/ 0 赞/ 160 阅读

相关 VALIDATION PROBLEMS WERE FOUND problem:错误

错误 VALIDATION PROBLEMS WERE FOUND problem: cvc-enumeration-valid: string value '3.0'

青旅半醒/ 2022年08月08日 15:52/ 0 赞/ 24 阅读

相关 Problem H

Problem H Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/

妖狐艹你老母/ 2022年06月14日 06:00/ 0 赞/ 156 阅读

相关 Problem E

Problem E Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/

以你之姓@/ 2022年06月13日 21:06/ 0 赞/ 206 阅读

相关 Problem Description

一批幸福的列车即将从杭州驶向幸福的终点站——温州，身为总列车长的linle有一些奇怪的癖好。他会记录下全部乘客的名字（name）和他们的人品值（RP），根据这些将他们排序

亦凉/ 2022年06月12日 07:27/ 0 赞/ 179 阅读

相关 Sum Problem

[http://acm.hdu.edu.cn/showproblem.php?pid=1001][http_acm.hdu.edu.cn_showproblem.php_pid

柔光的暖阳◎/ 2022年03月22日 13:20/ 0 赞/ 181 阅读

相关 Flow Problem

Problem Description Network flow is a well-known difficult problem for ACMers. Given a

Myth丶恋晨/ 2022年01月05日 15:27/ 0 赞/ 283 阅读

相关 Problem 8

Problem 8 Problem_8.py """ The four adjacent digits in the 1000-digit nu

淡淡的烟草味﹌/ 2021年12月14日 07:43/ 0 赞/ 181 阅读

相关 Problem 20

Problem 20 问题网址：[https://projecteuler.net/problem=20][https_projecteuler.net_problem_

妖狐艹你老母/ 2021年12月14日 07:41/ 0 赞/ 207 阅读