笔记精选

import sys
n = eval(input())
nums = [int(i) for i in sys.stdin.readline().split()]
dp = [0 for _ in range(n+2)]
dpNum = [0 for _ in range(n+2)]
num = 0
for i in range(n-1, -1, -1):
    if dp[i+1] < dp[i+2]+nums[i]:
        dp[i] = dp[i+2]+nums[i]
        dpNum[i] = dpNum[i+2]+1
    else:
        dp[i] = dp[i+1]
        dpNum[i] = dpNum[i+1]
print(dp[0], dpNum[0])

#include <iostream>
#include <vector>
using namespace std;

// dp[i]: 从第一篇笔记开始选到第i篇, 所能得到的最大点赞数。
// count[i]: 此时选取的笔记数量
int main(){
    int n, val;
    cin >> n;
    vector<int> vec(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        cin >> val;
        vec[i] = val;
    }
    vector<int> dp(n + 1, 0);  
    vector<int> count(n + 1, 0);
    dp[1] = vec[1];  //选第一篇笔记, 最大点赞数自然就是vec[1]
    count[1] = 1;    //选了一个数
    for(int i = 2; i <= n; ++i){
        //选了dp[i - 2], 就不能选dp[i - 1], 但可以选vec[i](不能连续)
        if(dp[i - 1] < dp[i - 2] + vec[i]){
            dp[i] = dp[i - 2] + vec[i];
            count[i] = count[i - 2] + 1;
        } else{
            //不选dp[i - 2]和vec[i]
            dp[i] = dp[i - 1];
            count[i] = count[i - 1];
        }
    }
    cout << dp[n] << ' ' << count[n] << endl;
    return 0;
}

def getMaxStar(n,nums):
    dp = [0 for _ in range(n+1)]
    dp2 = [0 for _ in range(n+1)]
    dp[1] = nums[0]
    dp2[1] = 1
    for i in range(2,n+1):
        if dp[i-1] < dp[i-2]+nums[i-1]:
            dp[i] = dp[i-2]+nums[i-1]
            dp2[i] = dp2[i-2]+1
        else:
            dp[i] = dp[i-1]
            dp2[i] = dp2[i-1]
    print(dp[-1], dp2[-1])
    
n = eval(input())
nums = [int(i) for i in input().split()]
getMaxStar(n, nums)
	

		
	

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> v(n+1);
        int num=0;
        for(int i=1;i<=n;i++)
        {
            cin>>num;
            v[i]=num;
        }
        int dp[n+1];
        int dpNum[n+1];
        memset(dpNum,0,sizeof dpNum);
        memset(dp,0,sizeof dp);
        dp[1]=v[1];dpNum[1]=1;
        for(int i=2;i<=n;i++)
        {
            if(dp[i-2]+v[i]>dp[i-1])
            {
                dp[i]=dp[i-2]+v[i];
                dpNum[i]=dpNum[i-2]+1;
            }
            else{
                dp[i]=dp[i-1];
                dpNum[i]=dpNum[i-1];
            }
        }      
        cout<<dp[n]<<" "<<dpNum[n]<<endl;
    }
    return 0;
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        int[] dp = new int[n+1]; // 总点赞数
        dp[1] = nums[0];
        int[] dpN = new int[n+1]; // 挑选笔记数
        dpN[1] = 1;
        for(int i = 2; i <= n; i++) {
            if(dp[i-1] < dp[i-2] + nums[i-1]) { // 选
                dp[i] = dp[i-2] + nums[i-1];
                dpN[i] = dpN[i-2] + 1;
            } else { // 不选
                dp[i] = dp[i-1];
                dpN[i] = dpN[i-1];                
            }
        }
        System.out.println(dp[n] + " " + dpN[n]);
    }
}

这个问题可以通过动态规划来解决。我们定义两个数组dp和count，其中：

• dp[i]表示在前i篇笔记中能获得的最多点赞数。
• count[i]表示在前i篇笔记中能获得dp[i]个点赞数所需要的最少笔记数。

动态规划的状态转移方程如下：

• 如果不选第i篇笔记，则有dp[i] = dp[i-1]，并且count[i] = count[i-1]。
• 如果选第i篇笔记，则有dp[i] = dp[i-2] + likes[i]（第i篇笔记的点赞数），并且count[i] = count[i-2] + 1。

初始化：

• dp[0] = likes[0]，count[0] = 1
• dp[1] = max(likes[0], likes[1])，count[1] = 1 if likes[0] < likes[1] else 1

最终结果为dp[n-1]和count[n-1]。

def select_notes(n, likes):
    if n == 0:
        return 0, 0
    if n == 1:
        return likes[0], 1

    # 初始化dp和count数组
    dp = [0] * n  # 在前 i 篇笔记中能获得的最多点赞数
    count = [0] * n  # 在前 i 篇笔记中能获得 dp[i] 个点赞数所需要的最少笔记数

    dp[0] = likes[0]
    count[0] = 1

    dp[1] = max(likes[0], likes[1])
    count[1] = 1  # 不能选连续的，只能二选一，选大的

    for i in range(2, n):
        if dp[i - 1] >= dp[i - 2] + likes[i]:  # 只是>不行，无法使笔记数最小
            dp[i] = dp[i - 1]
            count[i] = count[i - 1]
        else:
            dp[i] = dp[i - 2] + likes[i]
            count[i] = count[i - 2] + 1

    return dp[-1], count[-1]


# 输入处理
n = int(input())
likes = list(map(int, input().split()))

import java.util.*;

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] upvotes = new int[n];
        for (int i = 0; i < n; i++)
            upvotes[i] = scanner.nextInt();
        int[][] dp = new int[n + 1][2];
        dp[1][0] = upvotes[0];
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (dp[i - 1][0] < dp[i - 2][0] + upvotes[i - 1])
            {
                dp[i][0] = dp[i - 2][0] + upvotes[i - 1];
                dp[i][1] = dp[i - 2][1] + 1;
            }
            else if (dp[i - 1][0] > dp[i - 2][0] + upvotes[i - 1])
            {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1];
            }
            else
            {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][1], dp[i - 2][1] + 1);
            }
        }
        System.out.println(dp[n][0] + " " + dp[n][1]);
    }
}

n = int(input())
line = [int(i) for i in input().split()]

if n == 0:
    print(0, 0)
elif n == 1:
    print(line[0], 1)
else:
    # dp[i] 表示考虑到第 i 篇笔记时的最大点赞总数
    dp = [0] * n
    # count[i] 表示达到 dp[i] 的点赞总数时所选笔记的最少数量
    count = [0] * n
    
    dp[0] = line[0]
    count[0] = 1
    dp[1] = max(line[0], line[1])
    count[1] = 1 if line[0] > line[1] else 1
    
    for i in range(2, n):
        if dp[i-2] + line[i] > dp[i-1]:
            dp[i] = dp[i-2] + line[i]
            count[i] = count[i-2] + 1
        elif dp[i-2] + line[i] == dp[i-1]:
            dp[i] = dp[i-2] + line[i]
            count[i] = min(count[i-2] + 1, count[i-1])
        else:
            dp[i] = dp[i-1]
            count[i] = count[i-1]

    print(dp[-1], count[-1])