[bzoj1082]-[SCOI2005]栅栏

发布于 2017-09-06  118 次阅读



题目(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;
}