UVA 10651

這道題有兩種做法：搜索和狀態壓縮dp

因為這個題的狀態只要2^12,所以可以用dfs或bfs將所有的可達狀態走一遍，然後就可以得到答案了。

我是用二進制壓縮以後再進行的dfs；其實也可以直接開一個12位長度數組表示狀態，然後dfs或bfs，這樣

狀態判重可以用hash或二進制壓縮。

狀態壓縮dp的話，現在還沒看，就放到以後再研究去了。

代碼如下：

#include
#include
#include
using namespace std;

int vis[5000],ans;

void dfs(int st)
{
    int a[20];
    int k=0;
    memset(a,0,sizeof(a));
    while(st)
    {
        a[k++]=st%2;
        st/=2;
    }
    k=12;
    for(int i=k-1;i>=2;i--)
    {
        if(a[i]==0&&a[i-1]==1&&a[i-2]==1)
        {
            int b[30];
            for(int j=0;j=0;j--)
            {
                if(b[j]==1)
                  cnt++;
                if(b[j]==1)
                  sum=sum*2+1;
                else
                  sum=sum*2;
            }
            if(cnt!=0&&cnt=0;j--)
            {
                if(b[j]==1)
                  cnt++;
                if(b[j]==1)
                  sum=sum*2+1;
                else
                  sum=sum*2;
            }
            if(cnt!=0&&cnt