1.3.2 Barn Repair 修理牛棚

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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注