题目描述

难度分:$1700$

输入$n(2 \leq n \leq 100)$和长为$n$的数组$a(1 \leq a[i] \leq 2000)$。

你需要删除$a$中的一些数，使$a$无法分成两个元素和相等的子序列。

输出最少要删除多少个数，以及这些数的下标（从$1$开始）。

注：子序列不要求连续。

输入样例$1$

4
6 3 9 12

输出样例$1$

1
2

输入样例$2$

2
1 2

输出样例$2$

0

算法

分类讨论+01背包

先可以分类讨论，令$sum=\Sigma_{i=1}^{n}a[i]$

1. 如果$sum$是个奇数，那根本就不用删任何数，肯定不能将$a$划分成两个累加和相等的子序列。
2. 如果$sum$是个偶数，但是无法凑出和等于$\frac{sum}{2}$的子序列，那也不用删任何数。可以用01背包来判断，此时问题转化成了每个数可以取也可以不取，是否可以凑出一个和为$\frac{sum}{2}$的子集，定义状态$dp[i]$为是否可以凑出$i$。如果凑得出$\frac{sum}{2}$，就需要删数，此时$sum$为偶数，随便删掉一个奇数就行；如果没有奇数，注意到将所有$a[i]$反复除以$2$答案是不变的，因此只需要不断除以$2$直到出现一个奇数即可（不需要真正除以$2$，出现奇数的时候一定每个数都已经除以了$min_{i=1}^{n}lowbit(a[i])$，因此$lowbit$值最小的那个数就是需要删除的数）。

复杂度分析

时间复杂度

算法流程的瓶颈在于01背包，时间复杂度为$O(nm)$，其中$m=\frac{\Sigma_{i=1}^{n}a[i]}{2}$。这里值得一提的是，如果是$sum$为偶数，且凑不出和为$\frac{sum}{2}$的子序列，同时所有$a[i]$都是偶数的情况下，找到$lowbit$最小值对应的索引时间复杂度为$O(n)$；即使按照所有数不断除以$2$来实现，时间复杂度也只有$O(nlog_2A)$，本题中$A \leq 2000$，最多除以$10$次左右一定会出现奇数，所以这一部分不会成为算法的瓶颈。

空间复杂度

空间瓶颈也是01背包的DP数组$dp$，优化掉第一维后额外空间复杂度为$O(m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int n, a[N];

int lowbit(int x) {
    return x&-x;
}

int main() {
    scanf("%d", &n);
    int tot = 0, index = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        tot += a[i];
        if(a[i]&1) {
            index = i;
        }
    }
    if(tot&1) {
        puts("0");
        exit(0);
    }
    int target = tot >> 1;
    bool dp[target + 1] = {0};
    dp[0] = true;
    for(int i = 1; i <= n; i++) {
        for(int j = target; j >= a[i]; j--) {
            dp[j] |= dp[j - a[i]];
        }
    }
    if(dp[target]) {
        if(index) {
            printf("%d\n%d\n", 1, index);
        }else {
            int minlowbit = lowbit(a[1]);
            index = 1;
            for(int i = 2; i <= n; i++) {
                if(lowbit(a[i]) < minlowbit) {
                    minlowbit = lowbit(a[i]);
                    index = i;
                }
            }
            printf("%d\n%d\n", 1, index);
        }
    }else {
        puts("0");
    }
    return 0;
}