C++ 解法, 执行用时: 13ms, 内存消耗: 2732KB, 提交时间: 2022-03-14

#include<bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#ifdef zz
#define de(i)         cout << i << ' '
#define den(i)         cout << i << endl
#define dea2(a,n,m)    rep(_i, 0, n) { rep(_j, 0, m) O(a[_i][_j]); puts(""); }
#define dea2n(a,n,m)    rep(_i, 1, n+1) { rep(_j, 1, m+1) O(a[_i][_j]); puts(""); }
#define dea(a,n)	       rep(_i,0,n)O(a[_i]);puts("")
#define dean(a,n)	       rep(_i,1,n+1)O(a[_i]);puts("")
#else 
#define de(i)           1
#define dean(a,n)       1
#define dea2n(a,n,m)    1
#define den(i)          1
#define dea2(a,n,m)    1
#define dea(a,n)	        1
#endif
#define rep(i, j, n)    for(int i=(j);i<(n);i++)
#define per(i, n, j)    for(int i=(n)-1;i>=(j);--i)
#define SIZE(a)         ((int)a.size())
#define ALL(a)          a.begin(), a.end()
//#define LL              ((l + r) >> 1)
#define I(i)            scanf("%d",&i)
#define O(i)            printf("%d ",i)
#define On(i)           printf("%d\n",i)
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch == '-' ? f = -1 : 0, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return (f == 1) ? x : -x;
}
//#define RR              (LL + 1)
#define move int dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 }
typedef long long           LL;
typedef unsigned long long  ULL;
#define PII pair<int,int>
#define VI vector<int>
#define pqs(i)          priority_queue<i, vector<i>, greater<i>> 
const int inf = 0x3f3f3f3f;
const int N6 = 1000000 + 10;
const int N5 = 100000 + 10;
const int N4 = 10000 + 10;
const int N3 = 1000 + 10;
const int N2 = 100 + 10;
const int N1 = 10 + 10;
void print() { puts(""); }
template<typename T, typename... Ts>
void print(T a, Ts... b) {
    cout << a << ' ';
    print(b...);
}

template<typename T>
int sz(const T& x) { return x.size(); }

//------------------------------
int n;

int a[2 * N5];
long long dp[2 * N5];
int main() {
    n = read();
    rep(i, 0, n)a[i] = read();
    rep(i, 0, n) {
        dp[i] = a[i] + (i > 1 ? dp[i - 2] : 0);
        if (i > 0) dp[i] = max(dp[i], dp[i - 1]);
    }
    long long res = 0;
    rep(i, 0, n) {
        res = max(res, dp[i]);
    }
    // dea(dp, n);
    cout << res << endl;
}

C 解法, 执行用时: 16ms, 内存消耗: 1840KB, 提交时间: 2022-02-08

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    long long int a[n+1];
    long long int dp[n+1];
    long long int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    dp[0]=0;
    dp[1]=a[1];
    x=a[1];
    for(int i=2;i<=n;i++)
    {
        if(dp[i-2]+a[i]>=dp[i-1])
            dp[i]=dp[i-2]+a[i];
        else
            dp[i]=dp[i-1];
        if(dp[i]>x)
        {
            x=dp[i];
        }
    }
    printf("%lld\n",x);
    return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 1952KB, 提交时间: 2022-02-10

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

int n;
int a[200005];
int dp[200005];


int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    dp[0]=0;dp[1]=a[1];
    for(int i=2;i<=n;i++){
        dp[i]=max(dp[i-2]+a[i],dp[i-1]);
    }
    printf("%d",dp[n]);
    return 0;
}

C 解法, 执行用时: 21ms, 内存消耗: 1864KB, 提交时间: 2022-04-20

#include<stdio.h>
int getmax(int a, int b){
    return a > b ? a : b;
}
int main(){
    int n;
    scanf("%d",&n);
    int i;
    int* num = (int*)malloc(4*n);
    int* dp = (int*)malloc(4*n);
    for(i = 0; i < n;i++){
        scanf("%d",&num[i]);
    }
    if(n == 1){
        printf("%d",num[0]);
        return 0;
    }
    else if(n == 2){
        printf("%d",getmax(num[0],num[1]));
        return 0;
    }
    else if(n == 3){
        printf("%d",getmax(num[0] + num[2],num[1]));
        return 0;        
    }
    dp[0] = num[0];
    dp[1] = num[1];
    dp[2] = dp[0] + num[2];
    
    for(i = 3; i < n ;i++){
        dp[i] = num[i] + getmax(dp[i-2],dp[i-3]);
    }
    printf("%d",getmax(dp[n-2],dp[n-1]));
    return 0;
}

C 解法, 执行用时: 22ms, 内存消耗: 384KB, 提交时间: 2022-04-19

#include<stdio.h>

int main()
{
    long long n,dp[5]={0};
    scanf("%lld",&n);
    
    for(long long i=1;i<=n;++i)
    {
        scanf("%lld",&dp[i%5]);
        if(i>2)
            dp[i%5] = (dp[(i-2+5)%5]+dp[i%5])>(dp[(i-3+5)%5]+dp[i%5])?(dp[(i-2+5)%5]+dp[i%5]):(dp[(i-3+5)%5]+dp[i%5]);
    }
    printf("%lld",dp[(n-1+5)%5]>dp[n%5]?dp[(n-1+5)%5]:dp[n%5]);
    return 0;
}