笔记精选

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] f=new int[n+1];//总点赞数
        int[] count=new int[n+1];//挑选笔记数
        int[] up=new int[n+1];//每一篇的点赞数
       
        for(int i=1;i<=n;i++){
            up[i]=sc.nextInt();
        }
        count[1]=1;
        f[1]=up[1];
        for(int i=2;i<=n;i++){
            f[n]=Math.max(f[n-2]+up[n],f[n-1]);
            if(f[n]==f[n-1]){
                count[n]=count[n-1];
            }else{
                count[n]=count[n-2]+1;
            }
             }
        System.out.println( f[n]+" "+count[n]);
    }
}
//我这个有什么问题啊，我找不到，通过不了，呜呜呜

#include <iostream>
#include <vector>

using namespace std;
int buffer[10001];

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; ++i) cin >> buffer[i];
    
    vector<pair<int, int>> dp(n);
    for(int i=0; i<n; ++i){
        if(i == 0) dp[i].first = buffer[i], dp[i].second = 1;
        else{
            auto cur = buffer[i] + (i-2 >= 0 ? dp[i-2].first : 0);
            auto cnt = i-2 >= 0? dp[i-2].second +1 : 1;
            
            if(cur > dp[i-1].first) dp[i] = {cur, cnt};
            else dp[i] = dp[i-1];
        }
    }
    cout << dp.back().first << ' ' << dp.back().second;
    return 0;
}

本题是动态规划问题，设 dp[i] 为前 i 个物品的最大挑选赞数， 状态转移方程是dp[i]=max(dp[i-1], dp[i-2]+nums[i])

#include<bits/stdc++.h>

using namespace std;

#define MAX_N 1010
int N;
int nums[MAX_N];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &nums[i]);
    }

    int dp_0 = 0;
    int dp_1 = 0;
    int num_0 = 0, num_1 = 0;
    for (int i = 0; i < N; ++i) {
        int temp = dp_1;
        int num_temp = num_1;
        if (dp_1 < dp_0+nums[i]) {
            dp_1 = dp_0+nums[i];
            num_1 = num_0+1;
        }
        dp_0 = temp;
        num_0 = num_temp;
    }

    printf("%d %d\n", dp_1, num_1);
    return 0;
}

var a = readline();
var c = readline();
c = c.split(" ");
    var b = c.map(item =>{
      return Number(item)
    })
var point = [];
var num = [];
point[0] = b[0];
num[0] = 1;
point[1] = Math.max(b[0],b[1]);
num[1] = 1;
for (var i = 2; i < b.length; i++) {
   if(b[i] + point[i - 2] > point[i - 1]){
       point[i] = b[i] + point[i - 2];
       num[i] = 1 + num[i-2];
    } else {
       point[i] = point[i - 1];
       num[i] = Math.min(num[i - 1] , 1 + num[i - 2])
    }
}
var res = [];
res.push(Math.max(...point));
let record = point.indexOf(res[0]);
res.push(num[record])
console.log(res[0] , res[1]) 

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=Integer.parseInt(sc.nextLine());
        int[] num=new int[n];
        for(int i=0;i<n;i++){
            num[i]=sc.nextInt();
        }
        int[] dp=new int[n+1];
        if(num.length==1){
            System.out.println(num[0]+" "+1);
        }
        if(num.length==2){
            System.out.println((num[0]>num[1]?num[0]:num[1])+" "+1);
        }
        
        dp[0]=num[0];
        dp[1]=num[0]>num[1]?num[0]:num[1];
        int[] dpN=new int[n];
        dpN[0]=1;
        dpN[1]=1;
        for(int i=2;i<n;i++){
            if(dp[i-1]<dp[i-2]+num[i]){
                dp[i]=dp[i-2]+num[i];
                dpN[i]=dpN[i-2]+1;
            }else{
                dp[i]=dp[i-1];
                dpN[i]=dpN[i-1];
            }
        }
        System.out.println(dp[n-1]+" "+dpN[n-1]);
        
    }
    
    
    
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] counts = new int[n];
        for(int i = 0; i < n; i++){
            counts[i] = in.nextInt();
        }
        //从右向左看，第i个开始的点赞数 
        //选取n+1作为容量且从1开始的原因是判断时需要n-2选项。dp[0]=0
        int[] dp = new int[n+1];
        dp[1] = counts[0];
        int[] cp = new int[n+1]; 
        //不赋值，初始值默认为0，不符合实际。
        cp[1] =1;
        for(int i=2;i<n+1;i++){
            //选取自己作为第一个与选取后一个比那一个更大
            if(dp[i-2]+counts[i-1]>dp[i-1]){
                dp[i] = dp[i-2]+counts[i-1];
                cp[i] = cp[i-2]+1;
            }else{
                dp[i] = dp[i-1];
                cp[i] = cp[i-1];
            }
        }
        System.out.println(dp[n]+" "+cp[n]);
    }
}

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let arr=line.split(' ')
        let dp=[]
        let g=[]
       
        if(arr.length<2) continue
        arr=arr.map((item)=>{
            return Number(item)
        })
        dp[0]=arr[0]
        dp[1]=arr[1]
        g[0]=1
        g[1]=1
        for(let i=2;i<arr.length;i++){
           dp[i]=Math.max(dp[i-1],dp[i-2]+arr[i])
           if(dp[i]==dp[i-2]+arr[i]){
              g[i]=g[i-2]+1
           }else{
              g[i]=g[i-1]
           }
        }
        console.log(dp[arr.length-1]+" "+g[arr.length-1])
    }
}()