/*
和P10120一模一样~
重题OTZ...
看那篇题解啦~
又练习了一遍~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1005;
const int MAXM=55;
int have[MAXM],fhave[MAXN];
int need[MAXN];
int sum,s[MAXN];
int m,n;
int mid;
int waste;
int ans;

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&have[i]);
        sum+=have[i];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&need[i]);
    sort(have+1,have+n+1);
    sort(need+1,need+m+1);
    for(int i=1;i<=m;i++)
        s[i]=s[i-1]+need[i];
}

bool dfs(int k,int cur)
{
    if(k<=0)
        return 1;
    if(sum-waste<s[mid])
        return 0;
    for(int i=cur;i<=n;i++)
        if(fhave[i]>=need[k])
        {
            fhave[i]-=need[k];
            if(fhave[i]<need[1])
                waste+=fhave[i];
            if(need[k]==need[k-1])
            {
                if(dfs(k-1,i))
                    return 1;
            }
            else    if(dfs(k-1,1))
                return 1;
            if(fhave[i]<need[1])
                waste-=fhave[i];
            fhave[i]+=need[k];
        }
    return 0;
}

void work()
{
    while(sum<need[m])
        m--;
    int l=0,r=m;
    while(l<=r)
    {
        waste=0;
        for(int i=1;i<=n;i++)
            fhave[i]=have[i];
        mid=(l+r)>>1;
        if(dfs(mid,1))
            l=mid+1,ans=max(ans,mid);
        else
            r=mid-1;
    }
    cout<<ans<<endl;
}

int main()
{
    init();
    work();
}
     

暴搜加一点小小的剪枝。。。
#include<bits/stdc++.h>
#define pi acos(-1.0)
#define ll long long
#define N 40010
#define INF 1000000007
using namespace std;

int n,m;
int tot,ans,waste;
int a[N],b[N];
int sum[N];
int c[N];
bool dfs(int now,int p)
{
if(!now)

return true;
if(waste+sum[now]>tot)
return false;
for(int i=p;i<=n;i++)
{
if(c[i]>=b[now])
{
c[i]-=b[now];
if(c[i]<b[1]) waste+=c[i];
if(b[now]==b[now-1])
{
if(dfs(now-1,i))
return true;
}
else
{
if(dfs(now-1,1))
return true;
}
if(c[i]<b[1]) waste-=c[i];
c[i]+=b[now];
}
}
return false;
}

int judge(int mid)
{
memcpy(c,a,sizeof (int)*(n+1));
waste=0;
return dfs(mid,1);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),tot+=a[i];
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+m+1);
for(int i=1;i<=m;i++)
sum[i]=sum[i-1]+b[i];
if(sum[m]>tot)m--;
int l=0,r=m;
ans=0;
while(l<=r)
{
int mid=l+r>>1;
if(judge(mid))
ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
return 0;
}

跟P1020一模一样，顶多换了个壳子

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int m,n;

bool cmp(int i, int j){
return i > j;
}
int yu[52];
int hua[1000];
bool zhao[1002];
int main()
{
memset(zhao,0,sizeof(zhao));
cin>>n;
for(int i=0;i<n;i++)cin>>yu[i];
sort(yu, yu+n, cmp);

cin>>m;
for(int i=0;i<m;i++)
{
cin>>hua[i];
}
sort(hua,hua+m);

int aa=0;

for(int i=0;i<n;i++)
{
for(int k=aa;k<m;k++)
{
if(yu[i]-hua[k]>=0){yu[i]-=hua[k];aa=k+1;}

}
}
cout<<aa;
return 0;
}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

BT的剪枝！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

交了好多次的其中一个点莫名其妙的超时

莫名其妙的过了

我怎么觉得很像背包啊

就是几个容量的包啊

居然是重题

curimit，我也是

...直接提交P1020的程序。

USACO 4.1.2

NOCOW上有题解。

基本思想就是DFS+优化。

把蛋糕合成一个大背包，，

把嘴巴放进去（先排序方便），最多的数量可以知道，

然后搜索，去掉不可以的嘴巴，建议分支定界搜索。

ps:直接分支定界75分，3超时

优化1：当有相同的嘴巴大小时，记一个为I，一个为I+1，那I对应的蛋糕绝对可以容下I+1号嘴巴，那搜索可以跳过

优化2：嘴巴无法再切下蛋糕时(m[i]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

IDDFS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 556ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：556ms

二分+深搜，但是我有一个点始终很慢——而且还是错的，结果我采用了——面向数据的编程方式……表BS我*_*

我的明显的错误的 贪心+搜索 程序 竟然也过了。

不是算法错误，而是中间操作有错误。

标准算法的确是搜索，而且是递增的搜索（虽然我的同学用的是”二分答案+搜索“差一点过了）

而胡伟栋大牛提出了一个”二分答案+普通贪心+随机贪心“的算法，虽然答案会有一些不稳定，但是还是可以过的

标准算法是搜索吧，好象要＋蛮多剪枝，所以我就遍了个贪心，结果就过了．．．

这不就是USACO4.1里的么

VIJOS前面买蛋糕那题也已经有了 怎么还有重复的..

郁闷ING

搜索怎样剪枝

同楼下...