1.3.2 Barn Repair 修理牛棚
时间： 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]）：
/*
ID: your_id_here
PROG: barn1
LANG: C++
*/
#include <iostream>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
int data[200];
struct Node
{
int d,n;
}node[50];
void update(int d,int n,int m)
{
int min=1000,n1=0;
for(int i=0;i<m-1;i++)
{
if(node[i].d<min)
{
min=node[i].d;
n1=i;
}
}
if(d>min)
{
node[n1].d=d;
node[n1].n=n;
}
}
int cmp(Node n1,Node n2)
{
if(n1.n<n2.n)return 1;
else return 0;
}
int main()
{
ofstream fout ("barn1.out");
ifstream fin ("barn1.in");
int m,s,c;
cin>>m>>s>>c;
for(int i=0;i<m;i++)
{
node[i].d=0;node[i].n=i;
}
for(int i=0;i<c;i++)
cin>>data[i];
sort(data,data+c);
for(int i=1;i<c;i++)
{
update(data[i]-data[i-1],i,m);
}
int sum=0;
sort(node,node+m-1,cmp);
if(m>=2)
{
int t=m;
for(int i=0;i<(m-1<c-1?m-1:c-1);i++)
{
//cout<<node[i].d<<" "<<node[i].n<<endl;
if(i==0)
sum+=data[node[i].n-1]-data[0];
else
sum+=data[node[i].n-1]-data[node[i-1].n];
//cout<<sum<<endl;
t--;
}
if(t==1)
cout<<sum+data[c-1]-data[node[m-2].n]+m<<endl;
else cout<<(m-1<c-1?m-1:c-1)+1<<endl;
}
else cout<<data[c-1]-data[0]+1<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。