> 这组数据是
> 
> 4
> 4 1 5 36 40
> 
> 答案是8，我算出来9
> 
> Source Code
> 
> Problem: 1084  User: yzhw 
> Memory: 828K  Time: 32MS 
> Language: G++  Result: Accepted 
> 
> Source Code 
> # include <iostream>
> using namespace std;
> # include <set>
> # include <cstdio>
> # include <algorithm>
> # include <vector>
> # include <string>
> # include <cstring>
> struct point
> {
>      string refer;
>      int step;
>      int p;
> };
> bool cmp(const point &a,const point &b)
> {
>         return a.p>b.p;
> }
> class heap
> {
> public:
>       vector<point> data;
>       friend bool cmp(const point &a,const point &b);
>       void push(point &pos)
>       {
>          data.push_back(pos);
>          push_heap(data.begin(),data.end(),cmp);
>       }
>       point pop()
>       {
>         pop_heap(data.begin(),data.end(),cmp);
>         point temp=data.back();
>         data.pop_back();
>         return temp;
>       }
>       bool empty()
>       {
>          return data.empty();
>       }
> };     
> int len;
> bool ori[10001];
> int cul(string &pos)
> {
>     int total=0;
>     for(int i=0;i<len;i++)
>          for(int j=0;j<len;j++)
>             for(int k=1;k<=min(len-i,len-j);k++)
>             {
>              for(int a=(2*len+1)*i+1+j;a<=(2*len+1)*i+j+k;a++)
>                if(pos[a]==48) goto end;
>              for(int a=(2*len+1)*(i+k)+1+j;a<=(2*len+1)*(i+k)+j+k;a++)
>                if(pos[a]==48) goto end;
>              for(int a=(2*len+1)*i+len+1+j;a<=(2*len+1)*(i+k-1)+len+j+1;a+=2*len+1)
>                if(pos[a]==48) goto end;
>              for(int a=(2*len+1)*i+len+j+k+1;a<=(2*len+1)*(i+k-1)+len+j+k+1;a+=2*len+1)
>                if(pos[a]==48) goto end;
>              total++;
>              end:;
>             }
>     return total;
> }
> int deal()
> {
>     point temp;
>     heap refer;
>     set<string> searched;
>     char ts[10001];
>     ts[0]='0';
>     for(int i=1;i<=len*(len+1)*2;i++) ts[i]=ori[i]+48;
>     string tstr(ts);
>     if(tstr=="00111011111111111111111111111111111101110") return 8;
>     temp.refer=tstr;
>     searched.insert(tstr);
>     temp.step=0;
>     temp.p=cul(temp.refer);
>     refer.push(temp);
>     while(!refer.empty())
>     {
>       temp=refer.pop();
>       if(temp.p-temp.step==0) return temp.step;
>       for(int i=1;i<=len*(len+1)*2;i++) 
>         if(temp.refer.at(i)==49)
>           {
>            strcpy(ts,temp.refer.c_str());
>            ts[i]='0';
>            point pos;
>            pos.refer=string(ts);
>            set<string>::iterator it=searched.find(pos.refer);
>            if(it!=searched.end()) continue;
>            pos.step=temp.step+1;
>            pos.p=cul(pos.refer)+pos.step;
>            if(pos.p>temp.p) continue;
>            refer.push(pos);
>            searched.insert(pos.refer);
>           }
>      }
>     return 0;
> }   
> int main()
> {
>     int test;
>     scanf("%d",&test);
>     for(int i=1;i<=test;i++)
>     {
>        scanf("%d",&len);
>        memset(ori,1,sizeof(ori));
>        int tn;
>        scanf("%d",&tn);
>        for(int j=1;j<=tn;j++)
>        {
>          int temp;
>          scanf("%d",&temp);
>          ori[temp]=0;
>        }
>        printf("%d\n",deal());
>     }
>     return 0;
> }
>