b_wy_小易的考试成绩（01背包变种）

n 个题目，第 i 个题目的分数是 si。如果小易第 i 题目回答正确，他将得到 Si 分，否则该题目他将得到 0 分。
最终的考试得分是所有题目得分的总和。由于阅卷老师很讨厌数字 5，在阅卷时如果一个学生的考试总分中含有数字 5，那么阅卷老师将气愤地给他 0 分。
那么小易考试的最高得分是多少？

思路：不断地求组合肯定超时，这里用反向思维，用组合分数作为下标，值为True/False

def solve(A, n):
    s=sum(A)
    f=[False for i in range(s+1)]
    f[0]=f[s]=True
    for x in A:
        for j in range(s,x-1,-1): #01背包的核心就是循环的起始数值
            f[j]|=f[j-x]
    for i in range(s,-1,-1): #贪心找最大
        if f[i] and str(i).find('5')==-1:
            return i
    return 0
n = int(input())
A = list(map(int, input().split()))
print(solve(A,n))