笔试时间：2024年03月27日

历史笔试传送门：2023秋招笔试合集

第一题

题目

即将进入假期的小A打算做很多作业，因为小A每天的心情不同，所以他每天可以做的作业数量可能不同。聪明的小A知道一直做作业是对身体不好的，所以需要他给自己制订一份劳逸结合的假期作业计划，也就是在每次做作业后都需要休息1天或2天(不能不休息，也不能休息大于2天)，再继续做作业。爱学习的小A决定在假期的第1天或第2天开始做作业，那么他在假期内最多能做多少作业?

输入描述

第一行有1个正整数n，表示假期的天数;

第二行有n个正整数ai，表示小A每天能完成的作业数。

1≤n≤ 10000,0≤ai≤ 10000

输出描述

输出一行一个整数，表示小A在假期内最多能做的作业数。

样例输入

5

2 1 2 1 2

样例输出

6

参考题解

dp动态规划，参考leetcode打家劫舍。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;
int f[N][2];

int main() {
    int n;
    cin >> n;
    
    f[0][0] = 0;
    f[0][1] = -INF;
    
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        f[i][1] = f[i - 1][0] + v;
        f[i][0] = max(f[i - 1][1], f[i - 1][0]);
    }
    
    cout << max(f[n][0], f[n][1]) << endl;
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;
class Main{

    static int N = 100010,n,INF = 0x3f3f3f3f;
    static int[][] f = new int[N][2];


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        f[0][0]=0;
        f[0][1]=-INF;
        for(int i=1;i<=n;i++){
            int v = sc.nextInt();
            f[i][1] = f[i-1][0]+v;
            f[i][0] = Math.max(f[i-1][1],f[i-1][0]);
        }
        System.out.println(Math.max(f[n][0]