模拟赛题讲解[14]

来自 yukuai26 2022-08-06 noi.ac #2755

题目背景

$\text{yukuai26}$ 喜欢算术，但他又菜又爱玩，所以需要你的帮助

题目描述：

小明给你 $n$ 个正整数，他想取一些数加起来（可以取 $0$ 个数），问能得到的最大的能被 $3$ 整除的和是多少

输入格式：

第一行一个整数 $n$

第二行 $n$ 个正整数, 表示小明给你的 $n$ 个正整数

输出格式：

一个整数，表示最大的能被 $3$ 整除的和

输入1：

4
1 2 3 4

输出1：

输入2：

3
693 647 550

输出2：

数据范围：

总共 $10$ 个测试点

对于测试点 $1,2$，$n \leq 3$

对于测试点 $3$，$n \leq 10$

对于测试点 $4,5$，保证小明给你的数只有 $3$ 的倍数

对于测试点 $6$，保证小明给的数对 $3$取模为 $0$ 或 $1$

对于测试点 $7$，$a_i \leq 100$

对于所有测试点 $n \leq 100000 ,a_i \leq 1000$

题解：

解法一贪心

先把所有的数都加上

那么最后的和模 $3$ 只有 $3$ 种情况

$S\bmod 3=0$ 直接输出答案即可
$S\bmod 3=1$ 去掉一个最小的模 $3$ 余 $1$ 的数即可
$S\bmod 3=2$ 去掉「两个最小的模 $3$ 余 $1$ 的数」和「一个最小的模 $3$ 余 $1$ 的数」中的较小者即可

时间复杂度 $O(n\log n)$

代码没写，因为考场上dp过了

解法二 DP

对于每个数，我们可以看作重量为 $w_i = x \bmod 3,v_i=x$ 的物品

设 $f_{i,j}$ 表示只考虑前 $i$ 个物品，总和模 $3$ 为 $j$ 时的最大总和，则

$f_{i+1,(j+w_{i+1}) \,\bmod \,3} = \max\{f_{i,(j+w_{i+1}) \,\bmod \,3},f_{i,j}+v_{i+1}\}$

然后就是简单的01背包啦

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,o,res,w[N],v[N],f[N][3];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,x; i<=n; i++)
    {
        cin >> x;
        if(x%3==0) res+=x;
        else ++o,w[o]=x%3,v[o]=x;
    }
    memset(f,0xc0,sizeof(f));
    f[0][0]=0;
    for(int i=0; i<o; i++)
        for(int j=0; j<=2; j++)
            f[i+1][(j+w[i+1])%3]=max(f[i][(j+w[i+1])%3],f[i][j]+v[i+1]);
    cout << res+f[o][0] << '\n';
    return 0;
}