题目（BZOJ）
题目（vijos）
来说说这道题吧~
首先是40分做法：暴搜。
就像下面这份代码这样暴搜。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
int n,m;
int a[55];
int b[1005];
bool vis[1005];
int ans;
void dfs(int step,int now,int val)
{
if (step==m+1)
{
ans=max(ans,val);
return;
}
for (int i=1;i<=n;++i)
{
if (vis[i]) continue;
if (b[i]<=now)
{
vis[i]=1;
dfs(step,now-b[i],val+1);
}
vis[i]=0;
}
dfs(step+1,a[step+1],val);
}
int main()
{
scanf(
for (int i=1;i<=m;++i)
{
scanf(
}
scanf(
for (int i=1;i<=n;++i)
{
scanf(
}
dfs(1,a[1],0);
printf(
return 0;
}
然后50分做法：排序，可以加快一点速度。
用最大的木板去切小木板，切得越多越好。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
int n,m;
int a[55];
int b[1005];
bool vis[1005];
int ans;
bool cmp(const int &x,const int &y)
{
return x>y;
}
int h()
{
for (int i=1;i<n;++i)
if (!vis[i]) return i;
return n;
}
void dfs(int step,int now,int val,int k)
{
if (step==m+1)
{
ans=max(ans,val);
return;
}
if (b[k+1]>now)
{
dfs(step+1,a[step+1],val,h());
return;
}
for (int i=1;i<=n;++i)
{
if (vis[i]) continue;
if (b[i]<=now)
{
vis[i]=1;
dfs(step,now-b[i],val+1,i);
}
vis[i]=0;
}
}
int main()
{
scanf(
for (int i=1;i<=m;++i)
{
scanf(
}
scanf(
for (int i=1;i<=n;++i)
{
scanf(
}
sort(a+1,a+m+1,cmp);
sort(b+1,b+n+1);
dfs(1,a[1],0,0);
printf(
return 0;
}
然后是70分做法（不保证正确性，毕竟WA了一个点）。
既然要切得尽量多，那就让没法继续切的木板长度总和尽量小吧？
当然，如果能切得更多，那么剩余木板长度总和小就行了。
于是剪枝策略就像这样：记录当前模板总和只差，然后与最小的差比较，大于则剪掉。
（貌似就是这个地方有点问题）。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
template <class ___E> inline void read(___E &e)
{
e=0;bool ck=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
if(ck) e = -e;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
int n,m;
int a[55];
int b[1005];
bool vis[1005];
int ans;
int lastidx;
int cha=1e9;
inline bool cmp(const int &x,const int &y)
{
return x>y;
}
inline int h()
{
for (int i=1;i<n;++i)
if (!vis[i]) return i;
return n;
}
inline int ma(int idx)
{
return a[idx]/b[lastidx];
}
void dfs(int step,int now,int val,int k,int maxn,int nowmaxn,int sta,int nowcha)
{
if (step==m+1 || sta==n+1)
{
cha=min(cha,nowcha);
ans=max(ans,val);
return;
}
if (nowcha>=cha) return;
if (maxn==nowmaxn)
{
lastidx=h();
if (!ma(step+1))
{
cha=min(nowcha,cha);
ans=max(ans,val);
return;
}
dfs(step+1,a[step+1],val,lastidx,ma(step+1),0,lastidx-1,nowcha+now);
return;
}
else if (b[k]>now)
{
lastidx=h();
dfs(step+1,a[step+1],val,lastidx,ma(step+1),0,lastidx-1,nowcha+now);
return;
}
for (int i=sta;i<=n;++i)
{
if (vis[i]) continue;
if (b[i]<=now)
{
vis[i]=1;
dfs(step,now-b[i],val+1,i+1,maxn,nowmaxn+1,i,nowcha);
}
vis[i]=0;
}
}
int main()
{
read(m);
for (int i=1;i<=m;++i)
read(a[i]);
read(n);
for (int i=1;i<=n;++i)
read(b[i]);
sort(a+1,a+m+1,cmp);
sort(b+1,b+n+1);
lastidx=1;
dfs(1,a[1],0,lastidx,ma(1),0,1,0);
printf(
return 0;
}
来到了我们的100分做法！
没错！其实50分做法的排序是很显然的，然后可以发现：整个序列是单调的！
单调能想到什么？二分啊！
二分能切的个数，然后进行搜索下去，看能不能切到这么多，之后更新答案。
完毕。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,m;
int a[55],b[1005],b2[1005];
bool vis[1005];
int s[1005];
int ans;
int sum;
bool flag;
void dfs(int ai,int bi,int now,int x)
{
if (!bi)
{
flag=true;
}
while (ai<=m && a[ai]<b[1])
{
now+=a[ai];
ai++;
}
if (flag || ai>m || now+s[x]>sum) return;
int k=ai,k1=ai,k2=bi,k3=now;
if (b[bi]==b[bi+1] && bi!=x)
k=b2[bi+1];
int i;
for (i=k;i<=m;++i)
{
if (a[i]<b[bi]) continue;
b2[bi]=i;
a[i]-=b[bi];
bi--;
dfs(ai,bi,now,x);
ai=k1,bi=k2,now=k3;
a[i]+=b[bi];
}
}
int main()
{
scanf(
for (int i=1;i<=m;++i)
scanf(
scanf(
for (int i=1;i<=n;++i)
scanf(
sort(a+1,a+m+1);
sort(b+1,b+n+1);
while (b[n]>a[m]) n--;
int cnt=0;
for (int i=1;i<=m;++i)
if (a[i]>b[1]) a[++cnt]=a[i];
m=cnt;
for (int i=1;i<=m;++i) sum+=a[i];
for (int i=1;i<=n;++i) s[i]=s[i-1]+b[i];
int L=1,R=n;
while (L<=R)
{
int mid=(L+R)>>1;
flag=false;
dfs(1,mid,0,mid);
if (!flag) R=mid-1;
else L=mid+1,ans=mid;
}
printf(
return 0;
}
Comments NOTHING