想法其实比较简单, 我们考虑先假设往一个方向一直移动完, 这时候如果某一次移动后悔, 相当于反向走原来的两倍, 我们直接用01背包, 在最坏 O(nm) 的时间内找出能否拼凑出一个值,使得 sum(a)-value = 0 (mod n)
ac代码:
import sys from collections import deque from heapq import heappop,heappush from math import ceil,inf,sqrt input = sys.stdin.readline def solve(): n,m = map(int, input().split()) a = list(map(int, input().split())) for i in range(m): a[i] %= n su = sum(a) % n for i in range(n): a[i] = (2*a[i]) % n f = [0]*(su+1) f[0] = 1 for i in range(n): for j in range(su,a[i]-1,-1): f[j] += f[j-a[i]] print("YES" if f[su] != 0 else "NO") # for _ in range(int(input())): # solve() solve()
全部评论
(1) 回帖