[TIOJ 1634] 然後我哥就起笑了

作法：

原本他應該是有限背包問題，但他要問的是 1~s 都可以被湊出來的最大 s 是多少，而且用的東西都是 2 的冪次，也就是大的永遠都是小的因數，所以這有更簡潔的作法。

考慮如果現在可以湊出 1 ~ s ，那麼當 x 個 2^n 加進來時，如果 s >= (2^n) - 1 ，那他顯然可以湊出 1 ~ s + x * 2^n 了，如果沒有的話，那還是只能湊出 1 ~ s 。對於後者比較直觀，因為此時 s < (2^n) - 1 ，所以 s+1 < 2^n ，也就是如果我們想湊出 s+1 ，那完全不會動到 2^n 的，但之前就湊不出來了，所以加入 2^n 之後還是湊不出來。

再來是前者，我們現在可以湊出 1 ~ s + x * 2^n 了，那麼 s + x * 2^n + 1 如果也能被湊出，目前的答案就會更大了，但事實上可以證明：如果可以用給定數量的 2^0 , ... , 2^(n-1) 湊出一個大於 2^n 的數 y ，那麼一定可以用更少數量湊出 y - 2^n ，具體的構造方法大概是從高位往低位作，從需要 1 個 2^n => 需要 2 個 2^(n-1) => 需要 4 個 2^(n-2) => ... ，並且在可以消掉的地方消掉( 例如用了 1 個 2^(n-1) ，就馬上把需要的 2 個 2^(n-1) 減掉一個 )，這樣就可以了。所以由這個結論，如果 s + x * 2^n + 1 可以被前面 2^0 ~ 2^(n-1) 湊出來，那麼 s+1 就可以被前面的湊出來，矛盾。

code :

#include<bits/stdc++.h>
using namespace std;
main()
{
    int n ; scanf("%d",&n) ;
    int s=0 ;
    for(int i=0;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        if(s>=((1<<i)-1)) s+=x*(1<<i) ;
    }
    printf("%d\n",s+1) ;
}