修理牛棚

修理牛棚

时间： 1ms        内存：64M

描述：

在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。

给出:可能买到的木板最大的数目M(1<= M<=50);牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。

输入：

1 行: M ， S 和 C(用空格分开)
2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

输出：

单独的一行包含一个整数表示所需木板的最小总长度。

示例输入：

4 50 18
3 
4 
6 
8 
14
15 
16 
17 
21
25 
26 
27 
30 
31 
40 
41 
42 
43

示例输出：

25

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 205
#define min(a,b) (a>b?b:a)
int cmp(const void *a,const void *b)
{
	return (*(int *)a)-(*(int *)b);
}
int main()
{
	int m,s,c;
	while(scanf("%d%d%d",&m,&s,&c)==3){
		int i,j,dp[55][MAX]={0};
		int num[MAX]={0},res=1000000;
		for(i=1;i<=c;i++)
			scanf("%d",&num[i]);
		qsort(&num[1],c,sizeof(int),cmp);
		memset(dp,1,sizeof(dp));
		dp[1][1]=1;
		for(i=2;i<=c;i++)
			for(j=1;j<=m;j++){
				dp[j][i]=min(dp[j][i-1]+num[i]-num[i-1],dp[j][i]);
				dp[j+1][i]=dp[j][i-1]+1;
			}
		for(i=1;i<=m;i++)
			res=min(res,dp[i][c]);
		printf("%d\n",res);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
    int s[201]; 
    int c[201]; 
    int mb,np,n; 
    int i; 
    cin>>mb>>np>>n; 
    mb--; 
    for(i=0;i<n;i++) 
    { 
        cin>>s[i]; 
    } 
    sort(s,s+n); 
    for(i=1;i<n;i++) 
    { 
        c[i-1]=s[i]-s[i-1]-1; 
    } 
    int length=s[n-1]-s[0]+1; 
    sort(c,c+n-1); 
    for(i=n-2;i>=0;i--) 
    { 
        if(mb==0)break; 
        mb--; 
        length-=c[i]; 
    } 
    cout<<length<<endl; 
    return 0; 
} 

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。