模拟赛题讲解[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;
}