HDU 1059 - dividing
Problem : Given 6 tpyes of numbers, each type has a[i] numbers of that number, check if all the numbers can be divided into two set, the sum of each set is equal.
Solution : It's a knapsack problem. let f[i][j] means if j can be reached using first i type numbers. then f[i][j]=f[i-1][j]|f[i-1][j-n[i]]|f[i-1][j-2*n[i]]|...|f[i-1][j-a[i]*n[i]].
Optimization :
1. If f[i-1][j]=1, then f[i][j], f[i][j+n[i]], ..., f[i][j+a[i]*n[i]] can be set to 1. (Still O(sum(a[i])*sum(n[i]*a[i])) ).
2. If f[i-1][j]=1, then set f[i][j], f[i][j+n[i]], f[i][j+2*n[i]], ..., f[i][j+k*n[i]] to 1, where k<=a[i] and f[i-1][j+n[i]], f[i-1][j+2*n[i]], ..., f[i-1][j+k*n[i]] are all 0 but f[i-1][j+(k+1)*n[i]] is 1. (The point: if j+l*n[i] (l>k) need to be set to 1. Since f[i-1][j+(k+1)*n[i]] is 1, f[i][j+l*n[i]] will be set to 1 at the (l-k-1)-th step of f[i-1][j+(k+1)*n[i]]'s update).
With the optimization 2, any number x will be set to 1 by number non-x at most once. Thus the Time Complexity reduce to O(sum(n[i]*a[i])).