> 给不停WA/TLE的C++ er们一点参考
> code很丑，见谅……
> 
> #include <iostream>
> #include <algorithm>
> using namespace std;
> 
> bool tie;
> int n,m,t,i,a[100],b[100],x[100],used[100],tx[100],tmax[10];
> int ans,ansnum,ansmax,ansrec[100];
> int mmax,num,tnum,last;
> 
> bool same()
> {
>      if (num!=ansnum) return false;
>      for (int iii=0;iii<num;iii++)
>          if (ansrec[iii]!=x[iii]) return false;
>      return true;
> }
> void dfs(int get,int kind)
> {
>      if (get==b[i])
>      {      
>         if ((kind>ans)||((kind==ans) &&(ansnum>num))||((kind==ans)&&(ansnum==num)&&(mmax>ansmax)))
>         {
>                      tie=false;
>                      ans=kind;
>                      ansnum=num;
>                      ansmax=mmax;
>                      for (int iii=0;iii<num;iii++) ansrec[iii]=x[iii];
>                      return;
>         };
>         if ((kind==ans)&&(ansnum==num)&&(ansmax==mmax)&&(!same())) 
>         {
>         tie=true;
>         return;
>         }
>         return;
>      }
>      if ((get>b[i])||(num>=4)) return;
>      for (int ii=last;ii<n;ii++)
>      {
>          used[ii]++;
>          tmax[num]=mmax;
>          num++;
>          last=ii;
>          mmax=a[ii]>mmax?a[ii]:mmax;
>          x[num-1]=ii;
>          dfs(get+a[ii],kind+(used[ii]==1));
>          mmax=tmax[num];
>          num--;
>          used[ii]--;
>      }
> }
>             
> void solve()
> {
>      for (i=0;i<m;i++)
>      {
>          
>          for (int j=1;j<=4;j++) x[j]=0;
>          for (int j=0;j<m;j++) used[j]=0;
>          tie=false;
>          mmax=0;
>          num=0;
>          ans=0;
>          ansmax=0;
>          ansnum=10000;
>          last=0;
>          dfs(0,0);
>          if (!ans) {cout<<b[i]<<" ---- none"<<endl; continue;}
>          cout<<b[i]<<" ("<<ans<<")"<<": ";
>          if (tie) cout<<"tie"<<endl;
>          else 
>          {
>               for (int ii=0;ii<ansnum-1;ii++) cout<<a[ansrec[ii]]<<" ";
>               cout<<a[ansrec[ansnum-1]]<<endl;
>               }
>      }
> }
> int main()
> {
>     while (cin>>t)
>     {
>           n=1; a[0]=t; cin>>t;
>           while (t) {n++; a[n-1]=t; cin>>t;}
>           m=0; cin>>t;
>           while (t) {m++; b[m-1]=t; cin>>t;}
>           solve();         
>     }
>     return 0;
> }   
发现有问题呀，给你一个测试数据。
stamp: 
84 54 59 13 41 56 32 5 84 88 25 61 13 40 88 85 12 84 67 12 8 24 40 58 82 14 56 54 6 12  0
customer: 
80 66 45 1 56 90 59 53 55 9 40 73 99 54 21 30 17 79 92 88 55 72 32 55 45 69 33 7 31 40  0
其中的 客户请求若为 55 ，则你代码码给出的最优解为13 5 13 24 。而最优解应该为 32 5 12 6 。程序中对tie的判断应该还有问题。

• Re:AC C++ code (359) hehaiqian 2010-12-31 10:43:57