记录编号	408654	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.995 s
提交时间	2017-05-25 10:47:18	内存使用	42.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
int n,w;
int dp[1<<19];
int wei[50];
int last[1<<19][20];
//int ji[1<<19][20];
void check(int now,int x,int next)
{
     pos(i,1,dp[now])
     {
        if(last[now][i]>=wei[x])
        {
           if(dp[now]<dp[next])
           {
              dp[next]=dp[now];
              last[now][i]-=wei[x];
              memset(last[next],0,sizeof(last[next]));
              pos(j,1,dp[now])
              {
                  last[next][j]=last[now][j];
              }
              last[now][i]+=wei[x];
              return;
           }
        }
     }
     if(dp[now]+1<dp[next])
     {
        dp[next]=dp[now]+1;
        memset(last[next],0,sizeof(last[next]));
        pos(j,1,dp[now])
        {
           last[next][j]=last[now][j];
        }
        last[next][dp[now]+1]=w-wei[x];
        return;
     }
     return;
}
int main()
{
    freopen("koneko.in","r",stdin);
    freopen("koneko.out","w",stdout);
    memset(dp,0x3f,sizeof(dp));
    scanf("%d%d",&n,&w);
    pos(i,1,n)
      scanf("%d",&wei[i]);
    pos(i,1,n)
    {
       dp[1<<(i-1)]=1;
       last[1<<(i-1)][1]=w-wei[i];
    }
    dp[0]=0;
    pos(i,0,(1<<n)-1)
    {
         pos(j,1,n)
         {
            if(i&(1<<(j-1)))
            {
              
               int temp=i^(1<<(j-1));
                //cout<<"i="<<i<<"   j="<<j<<"  i&(1<<(j-1))="<<(i&(1<<(j-1)))<<"   temp="<<temp<<"   dp[temp]="<<dp[temp]<<endl;
               sort(last[temp]+1,last[temp]+dp[temp]+1);
               check(temp,j,i); //cout<<dp[(1<<n)-1]<<endl;
            }
         }
    }
    cout<<dp[(1<<n)-1];
    //while(1);
    return 0;
}