1082: [SCOI2005]栅栏
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 969 Solved: 446
[Submit][Status][Discuss]
Description
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。
Input
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。接下来一行(即第m+2行)为整数n(n <= 1000)，表示约翰需要多少木材。接下来n行表示他所需要的每一块木板的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。
Output
只有一行，为约翰最多能够得到的符合条件的木板的个数。
Sample Input
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
Sample Output
7
HINT
25切出 21 30切出 20 40切出 19、18 50切出 15、16、17
Source
看到这道题莫名的熟悉感。。。瞬间发现是USACO的题目。。。看来我做过的题目还是可以记住的
题目还是很简单的，总体思路是二分答案+DFS验证
对输入的值进行排序，二分一个答案，显然取最小的边最优，然后找用来截的最小的木板，在加可行性剪枝什么的就可以过了。。具体见代码吧
细节：感觉这道题没什么细节、、、
#include <cstdio>
#include <algorithm>
using namespace std;
int a[60],b[1010],sum[1010],n,m,ans,need,rest,tot;
bool dfs(int x,int y){
if (rest+need>tot) return 0;
int ret = 0;
for (int i=y;i<=m;i++)
if (a[i]>=b[x]){
a[i]-=b[x];
if (a[i]<b[1]) rest+=a[i];
if (x==1) ret = 1;
else if (b[x]==b[x-1]) ret = dfs(x-1,i);
else ret = dfs(x-1,1);
rest-=a[i];
a[i]+=b[x];
if (ret) return 1;
}
return 0;
}
int main(){
scanf("%d",&m);
for (int i=1;i<=m;i++) scanf("%d",&a[i]),tot+=a[i];
sort(a+1,a+1+m);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
sort(b+1,b+1+n);
for (int i=1;i<=n;i++) sum[i] = sum[i-1]+b[i];
int l = 0,r = n;
while (l<=r){
int mid = (l+r)>>1;
need = sum[mid];rest = 0;
if (dfs(mid,1)){ans = mid;l = mid+1;}
else r = mid-1;
}
printf("%d",ans);
}
评论 (0)
