关于原题,请点这里
题目建模
给定一个长度为n的数组,判断某一个元素能不能用其它元素表示(每个元素可选无数次)
样例 and 结果
样例1
4
3 19 10 6
结果1
2
说明
6 = 2 * 3
19 = 10 + 3 * 3
样例2
5
11 29 13 19 17
结果2
5
DP做法(完全背包)
1、状态定义
定义f[i][j]为从前i-1个数中选择选择若干数字使得总和为j的方案数(判断能不能选到就是判断方案数是不是为0)
2、集合划分
从“第i-1个数”选择了几个入手对集合进行划分
3、初始状态
根据定义有f[0][…] = 0,f[1…][0] = 1, f[1][....] = 0
朴素版
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
a.sort()
f = [[0 for i in range(25010)] for i in range(110)]
f[1][0], res = 1, n
for i in range(2, 1 + n):
f[i][0] = 1#如果不加这句下面循环就需要从0开始,不过好像会TLE
for j in range(1, a[-1] + 1):
cnt = 0#cnt枚举第i-1选几个
while a[i - 1] * cnt <= j:
f[i][j] += f[i - 1][j - a[i - 1] * cnt]
cnt += 1
if f[i][a[i]]: res -= 1
print(res)
表达式优化
按照定义比较下f[i][j] 和f[i][j - a[i-1]]的含义即可
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
a.sort()
f = [[0 for i in range(25010)] for i in range(110)]
f[1][0], res = 1, n
for i in range(2, 1 + n):
f[i][0] = 1
for j in range(1, a[-1] + 1):
f[i][j] = f[i - 1][j]
if j >= a[i - 1]: f[i][j] += f[i][j - a[i - 1]]
if f[i][a[i]]: res -= 1
print(res)
空间优化:滚动数组
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
a.sort()
f = [0 for i in range(25010)]#st[i][j]前面i个数能不能表示j
f[0], res = 1, n
for i in range(2, 1 + n):
f[0] = 1#这句加不加无所谓
for j in range(a[i - 1], a[-1] + 1):
f[j] += f[j - a[i - 1]]
if f[a[i]]: res -= 1
print(res)