这组数据是

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;
}

• Re:。。。。A*函数设计有问题，不是相容的。。囧 (3374) yzhw 2009-05-21 15:46:36
• Re:大家帮帮忙，我有一组数据过不去，能帮忙查下程序不？我用特殊方法把那组数据AC了。。 (3374) qiuxinwei 2009-05-21 15:56:02