题意

一个数组分成两组

1. 5的倍数在一组
2. 是3的倍数 且 不是5的倍数 在另一组
3. 剩余数字自由分组

是否能让分成的两组数字的和相等

限制：数组长度不大于50，数值绝对值不大于500

方法

动态规划

先不考虑限制，分成两组和相等，也就是两组数字和的差为0,即是第一组的和 - 第二组的和 = 0

再看限制，不妨设，5的倍数在第一组，3的倍数 且 不是5的倍数在第二组

那么 第一组的和 - 第二组的和 = 0 变为

(5的倍数的和) - (3的倍数 且 不是5的倍数 的和) + (第一组剩余的和) - (第二组剩余的和) = 0

这里如果把和展开，实际上就是第一组的值全部 在表达式中是加法，第二组的值全部是减法

先处理掉确定部分的值，对于剩余值建立新数组

对于新数组设计状态

$dp[i][j]=dp[i][j]\; =$ 前i个数的和是否能达到j

有转移方程 $dp[i][j]=dp[i-1][j-val[i]]ordp[i-1][j+val[i]]dp[i][j]\; =\; dp[i-1][j-val[i]]\; or\; dp[i-1][j+val[i]]$

以题目样例数据为例

1 5 -5 1

首先我们把5的倍数的和放在第一组，是0.

然后，将 3的倍数 且 不是5的倍数 的和 放在第二组，也是0

上述的这个表达式 (5的倍数的和) - (3的倍数 且 不是5的倍数 的和) + (第一组剩余的和) - (第二组剩余的和) = 0

变为 0 - 0 + (第一组剩余的和) - (第二组剩余的和) = 0

新的数组为剩下的值1 1

这样，通过转移方程处理所有值后，最后的下标为0时，为可达，所以存在方案

注意到上面的运算可能会有负值，而数组下标一般时非负数，所以考虑增加一个偏移量，让所有值都非负，因为时偏移，所以对转移方程并不影响

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(~scanf("%d",&n)){
        int diff = 0;
        vector<int> arr;
        for(int i =0;i<n;i++){
            int v;
            scanf("%d",&v);
            if(v%5==0)diff+=v; // 第一组 含5
            else if(v%3==0)diff-=v; // 第二组 不含5且含3
            else arr.push_back(v);
        }
        // sum(group[1]) - sum(group[2]) == 0
        const int N = 50*500*2; // 50*500*2 = 50000
        // dp[idx][sum(group[1]) - sum(group[2]) + 50000/2] = bool
        vector<vector<bool> >dp(60,vector<bool>(N+10,false));
        dp[0][N/2 + diff] = true; // 下标 +平移25000 （偏移量）
        for(int i = 0;i<arr.size();i++){
            for(int v = 0; v <= N;v++){
                if(!dp[i][v]) continue;
                // 可达值
                if( v - arr[i] >= 0 && v - arr[i] <= N){ // 放在第二组
                    dp[i+1][v - arr[i]] = true;
                }
                if( v + arr[i] >= 0 && v + arr[i] <= N){ // 放在第一组
                    dp[i+1][v + arr[i]] = true;
                }
            }
        }
        printf("%s\n",dp[arr.size()][N/2]?"true":"false" ); // 因为加了偏移量 所以时判断 0 + N/2 = N/2
    }
    return 0;
}

复杂度分析

时间复杂度: 判断了所有位置，所有可能可达值是否可达，转移代价为常数，所以时间复杂度为$O(n^2\cdot val)O(n^2\backslash cdot\; val)$

空间复杂度: 主要消耗在，dp设计的状态储存，所以空间复杂度为$O(n^2\cdot val)O(n^2\; \backslash cdot\; val)$

滚动数组+DP空间优化

注意到 状态转移只和前一轮状态相关，所以可以考虑，把上上次的状态空间进行复用, 因此采取mod 2 的方式来复用数组。

需要注意的是，每次使用前记得清空数组。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(~scanf("%d",&n)){
        int diff = 0;
        vector<int> arr;
        for(int i =0;i<n;i++){
            int v;
            scanf("%d",&v);
            if(v%5==0)diff+=v; // 第一组 含5
            else if(v%3==0)diff-=v; // 第二组 不含5且含3
            else arr.push_back(v);
        }
        // sum(group[1]) - sum(group[2]) == 0
        const int N = 50*500*2; // 50*500*2 = 50000
        // dp[idx][sum(group[1]) - sum(group[2]) + 50000/2] = bool
        vector<vector<bool> >dp(2,vector<bool>(N+10,false)); // 使用滚动数组
        dp[0][N/2 + diff] = true; // 下标 +平移25000
        for(int i = 0;i<arr.size();i++){
            for(int v = 0; v <= N;v++){ // 因为是复用，注意清空
                dp[(i+1)%2][v] = false; // 坐标取 mod 2
            }
            for(int v = 0; v <= N;v++){
                if(!dp[i%2][v]) continue; // 坐标取 mod 2
                // 可达值
                if( v - arr[i] >= 0 && v - arr[i] <= N){ // 放在第二组
                    dp[(i+1)%2][v - arr[i]] = true; // 坐标取 mod 2
                }
                if( v + arr[i] >= 0 && v + arr[i] <= N){ // 放在第一组
                    dp[(i+1)%2][v + arr[i]] = true; // 坐标取 mod 2
                }
            }
        }
        printf("%s\n",dp[arr.size()%2][N/2]?"true":"false" ); // 坐标取 mod 2
    }
    return 0;
}

复杂度分析

时间复杂度: 判断了所有位置，所有可能可达值是否可达，转移代价为常数，所以时间复杂度为$O(n^2\cdot val)O(n^2\backslash cdot\; val)$

空间复杂度: 主要消耗在，dp设计的状态储存，所以空间复杂度为$O(n\cdot val)O(n\; \backslash cdot\; val)$