题解 | #数组分组#

#include <iostream>
#include <vector>
using namespace std;
int dp[64][2048], arr[64]; // t1 - t2 + 1000: [0, 2000]
int main() 
{
    int n, p=0, t, sum1 = 0, sum2 = 0;
    cin>>n;
    for(int i = 0; i<n;i++){
        cin>>t;
        if(t % 5 == 0)sum1 += t;
        else if(t%3 == 0) sum2 += t;
        else arr[++p]=t;
    }
    dp[0][sum1-sum2+1000]=1;
    for(int i = 1;i<=p;i++){
        for(int j = arr[i]; j+arr[i]<=2000; j++){
            // t1-(t2+arr[i])+1K = j -> t1-t2+1k = j+arr[i]
            dp[i][j] |= dp[i-1][j+arr[i]]; // put into t2
            // (t1+arr[i])-t2+1K = j -> t1-t2+1k = j-arr[i] 
            dp[i][j] |= dp[i-1][j-arr[i]]; // put into t1
        }
    }
    if(dp[p][1000])cout<<"true"<<endl;
    else cout<<"false"<<endl;
    return 0;
}

时间复杂度O(n*(max-min))

空间复杂度O(n*(max-min))