题解 | #数组分组#

#include <deque>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    deque<int>
    que; // que里面前面全是5的倍数，后面全是非5 3 的倍数
    int sum = 0;
    int pos = 0;
    int sumFive = 0;
    while (n--) {
        int i;
        cin >> i;
        if (i % 15 == 0 &&
                i != 0) { // 3 5的公倍数不能被分进任意一组 判断整除时永远要先讨论0！！！
            cout << "false";
            return 0;
        }
        // 若没有5的倍数， pos = 0；
        if (i % 5 == 0 && i != 0) { // 5的倍数从前面压进去
            que.push_front(i);
            sumFive += i;
            pos++;
        } else if (i % 3 != 0 || i == 0) { // 非5 3 的倍数从后面压进去
            que.push_back(i);
        }
        sum += i;
    }
    if (sum % 2 != 0 && sum != 0) { // sum是奇数，肯定分不出来
        cout << "false";
        return 0;
    }
    vector<int> nums;
    while (!que.empty()) {
        nums.push_back(que.front());
        que.pop_front();
    }
    sum /= 2;
    sum -= sumFive;
    sum += 25000;
    vector<int> dp(50000, 0); // dp[25000]对应 sum = 0
    dp[25000] = 1;
    int minIdx = 25000; // 需要记录一个能达到的最小数
    for (int i = pos; i < nums.size(); i++) {
        if (nums[i] >= 0) {
            for (int j = 50000; j >= nums[i] + minIdx;
                    j--) {    
                if (dp[j - nums[i]] == 1) {
                    dp[j] = 1;
                    // if (j < minIdx) minIdx = j;
                }
            }
        } else {
            for (int j = 0; j <= nums[i] + minIdx; j++) {   
                if (dp[j - nums[i]] == 1) {
                    dp[j] = 1;
                    if (j < minIdx) minIdx = j; // 更新最小idx
                }
            }
        }
    }
    cout << (dp[sum] == 1 ? "true" : "false");
}
// 64 位输出请用 printf("%lld")

双向动态规划。