删除相邻数字的最大分数

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

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

const int N = 1e4+10;

int a[N],f[N],n;

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

C++ 解法, 执行用时: 14ms, 内存消耗: 996KB, 提交时间: 2022-07-28

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

// const int N = 1e4+10;

// int a[N],f[N],n;

// int main()
// {
//     scanf("%d",&n);
//     for(int i=1;i<=n;i++)
//     {
//         int t;
//         scanf("%d",&t);
//         a[t]+=t;
//     }
    
//     f[1]=a[1];
//     for(int i=2;i<N;i++)
//     {
//         f[i]=max(f[i-1],f[i-2]+a[i]);
//     }
    
//     printf("%d\n",f[N-1]);
//     return 0;
// }
#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

/*
按元素值统计每个数出现的个数，总和即为该数得分
依题得分不能来自两个相邻的元素值
按取值遍历，同样用变量表示是否选择当前值即可
*/

int main() {
    int points[10001] = {0}; // 各个取值的得分
    int n;
    cin >> n;
    while (n--) {
        int i;
        cin >> i;
        points[i] += i;
    }
    long yes = 0, no = 0;
    for (int i = 1; i <= 10000; ++i) {
        long pre = no;
        no = max(yes, no); // 不选当前值的最大得分
        yes = pre + points[i]; // 选取当前值的最大得分
    }
    cout << max(yes, no) << "\n";
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 496KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

/*
按元素值统计每个数出现的个数，总和即为该数得分
依题得分不能来自两个相邻的元素值
按取值遍历，同样用变量表示是否选择当前值即可
*/

int main() {
    int points[10001] = {0}; // 各个取值的得分
    int n;
    cin >> n;
    while (n--) {
        int i;
        cin >> i;
        points[i] += i;
    }
    long yes = 0, no = 0;
    for (int i = 1; i <= 10000; ++i) {
        long pre = no;
        no = max(yes, no); // 不选当前值的最大得分
        yes = pre + points[i]; // 选取当前值的最大得分
    }
    cout << max(yes, no) << "\n";
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 524KB, 提交时间: 2022-07-22

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

const static int MAX_SIZE = 10001;
int a[MAX_SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    int max_val = 0;
    int min_val = 1000000;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        a[temp] += 1;
        max_val = max(max_val, temp);
        min_val = min(min_val, temp);
    }
    
    int v[max_val];
    for (int i = 0; i <= max_val; i++) {
        v[i] = 0;
    }
    v[1] = a[1];
    for (int i = max(1, min_val); i <= max_val; i++) {
        v[i] = max(v[i - 1], v[i - 2] + a[i] * i);
    }
    cout << v[max_val] << endl;
}

C 解法, 执行用时: 16ms, 内存消耗: 396KB, 提交时间: 2022-06-20

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int *a = (int *)malloc(sizeof(int) * 10010);
    int *f = (int *)malloc(sizeof(int) * 10010);
    memset(a, 0, sizeof(int) * 10000);
    memset(f, 0, sizeof(int) * 10000);
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        a[t] += t;
    }

    f[1] = a[1];
    for (int i = 2; i < 10010; i++) {
        f[i] = max(f[i-1], f[i-2] + a[i]);
    }
    
    printf("%d\n", f[10009]);
    
    free(a);
    free(f);
    
    return 0;
}

详情