bitset優化dp

以下是在codeforce找到的簡短敘述（ http://codeforces.com/blog/entry/45576 ）

Problem is: we have n numbers, calculate how many distinct numbers we can form by sum some of these numbers.

For example if we have set {17, 23, 40}, we can form {0, 17, 23, 40, 57, 63, 80}.

Dp solution is obvious:

dp[0] = 1;
for(int i = 0; i < n; i++)

for(int j = maxv - 1; j >= a[i]; j--)  
// maxv is some number bigger than sum of a[i]'s
dp[j] |= dp[ j - a[i] ];
cout << count(dp, dp + maxv, 1) << '\n';

Now how to optimize it? bitset can store bits and do operations 32 times faster like this:

bitset dp;
dp.set(0);
for(int i = 0; i < n; i++)
dp |= dp << a[i];
cout << dp.count() << '\n';

假設有三個數字 17,23,40 要求將三個數字相加後的所有可能解
<法一 >
暴力直接加加看
<法二>
宣告一個bitset(由一串01組成的數組)

bitset<1000>b;

第零位表示數字零是否可被加出來，第一位表示一可不可以被加出來，以此類推。
假設現在3,5,6可以被加出來，那麼要全部加9要怎麼加呢？
由剛剛定義的，可以列出以下狀態（從第零位開始列）
0 0 0 1 0 1 1 0 0 0 0
那全部加9會變這樣
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0
也就是全部往右9格，全部往右退九格，正式bitset厲害的地方，只需要

b<<9;

O(1)解決