Subset of Five

题目：Subset of Five
来源：吉林大学ACM集训队选拔赛（重现赛）

解题思路

集合 A 中有 n 个不同的整数。找出它的一个子集 S，使得 S 中元素之和能够被 5 整除，求 S 中元素之和的最大值。

res[i] 表示模为 i 时，当前元素之和的最大值。
pre[i] 表示模为 i 时，前一步元素之和的最大值。

C++代码

#include<iostream>
using namespace std;

long long pre[5];
long long res[5];

int main(){
    int n;
    cin >> n;
    int a;
    for(int i=0; i<n; ++i){
        cin >> a;
        for(int j=0; j<5; ++j){
            long long sum = pre[j] + a;
            int k = sum % 5;
            res[k] = max(res[k], sum);
        }
        for(int j=0; j<5; ++j)
            pre[j] = res[j];
    }
    cout << res[0] << endl;
    return 0;
}