[ CodeVS冲杯之路 ] P2456

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/2456/

　　用贪心的思想，木材当然要尽量分成多的木板，而大的木材能够分成大木板，但是小的木材不一定能够分成大的木板，所以木板和木材都是从小到大开始选，然后要保证剩余的木材最少

　　那么将木板和木材排序，对于每个木材，把能够分的小木板尽量分掉，如果遇到更大的木板则把最小的木板腾出来，然后在加上，这样保证剩余的木材最少

　　因为是上午写得这道题，思路可能不连贯了，代码应该描述的很清楚

　　虽然贪心在CodeVS上可以过，但是它是有数据可以卡掉的，而正解是DFS

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int N=,M=;

 int a[N],b[M],next[M];

 bool f[M];

 int main()

 {

     int n,i,j,m,k,now,ans=,x,y;

     scanf("%d",&n);

     for (i=;i<=n;i++) scanf("%d",&a[i]);

     sort(a+,a++n);

     scanf("%d",&m);

     for (i=;i<=m;i++) scanf("%d",&b[i]);

     sort(b+,b++m);

     for (i=;i<=n;i++)

         {

             now=a[i];

             for (j=;j<=m;j++) next[j]=;

             for (j=;j<=m;j++)

                 {

                     if (f[j]) continue;

                     if (now>=b[j])

                         {

                             now-=b[j];

                             f[j]=;

                             ans++;

                             next[j]=next[];

                             next[]=j;

                         }

                     else

                         {

                             k=x=;

                             while (now+b[next[k]]>=b[j]) k=next[x=k];

                             if (k)

                                 {

                                     next[x]=next[k];

                                     f[k]=;

                                     f[j]=;

                                     next[j]=next[];

                                     next[]=j;

                                     now+=b[k]-b[j];

                                 }

                         }

                 }

         }

     printf("%d\n",ans);

     return ;

 }

　　下面是DFS的正解，贴的别人的代码

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 #define N 1100

 int n,m;

 int sum1,ans;

 int tim,res;

 int a[N],b[N],c[N],sum[N];

 int work(int x,int k)

 {

     if (!x)

         return true;

     if (tim>res)

         return false;

     for (int i=k;i<=n;i++)

         if (a[i]>=b[x])

         {

             a[i]-=b[x];

             if (a[i]<b[])

                 tim+=a[i];

             if (b[x]==b[x-])

             {

                 if (work(x-,i))

                     return true;

             }

             else if (work(x-,))

                 return true;

             if (a[i]<b[])

                 tim-=a[i];

             a[i]+=b[x];

         }

     return false;

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++)

         scanf("%d",&a[i]),sum1+=a[i],c[i]=a[i];

     scanf("%d",&m);

     for (int i=;i<=m;i++)

         scanf("%d",&b[i]);

     sort(a+,a+n+);

     sort(b+,b+m+);

     for (int i=;i<=m;i++)

         sum[i]=b[i]+sum[i-];

     int l=,r=m;

     while (l!=r)

     {

         int mid=(l+r+)>>;

         tim=;

         res=sum1-sum[mid];

         if (work(mid,))

             l=mid;

         else

             r=mid-;

         for (int i=;i<=n;i++)

             a[i]=c[i];

     }

     printf("%d\n",l);

     return ;

 }