| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1359 人关注过本帖
标题:求解uva 10163 一道DP题ACM高手来
取消只看楼主 加入收藏
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
结帖率:75%
收藏
已结贴  问题点数:30 回复次数:4 
求解uva 10163 一道DP题ACM高手来
10163守仓库的人
背景:
蓝迪公司有N(1 < = N < = 100)个仓库。公司希望有人来看守它们。现在有M(1 < =M< = 30)人应聘这项工作,公司将雇佣一些人。蓝迪的公司以这些规则雇佣人:
1、每个看守人有一个数值Pi(1<=Pi<=1000),代表他们的能力值。
2、所有的仓库是一样的。
3、一个仓库只能被一个人看守,但一个人能看守几个仓库。如果一个看守的能力值是Pi,然后他看管K个仓库。他看管的每个仓库的安全值Uj=Pi div K。(Note:Uj、Pi、K是整型),没人照顾的仓库安全值是0。
4、如果所有的仓库给了人去看管,公司将达到一个安全线L=min(Uj)。(PS:这句话我翻译得很纠结,读者可以参照原句:4.If all the storages is at least given to a man, company will get a safe line L=min Uj)
5、每个月蓝迪公司会依据他们的能力值付给每个看守人工资,这意味着如果一个看守人的能力是Pi,则他的工资将是Pi美元/月。公司将支付所有的工资Y美元。
现在蓝迪公司给你一个报表包括所有的信息包括N、M、P,你的任务是给公司一个最佳选择,令公司在安全线L最高的前提下,付给看守人最少的工资。

输入:
输入文件包含多组数据
每组数据由两行组成:
第一行包含两个数字N和M
第二行有M个数字,表示每个守仓库的人的能力值。
相邻的两个数字间有一个空格。
当N=0,M=0时输入结束。
输出:
每个数据应输出最高的L和最小的Y,它们中间应有一个空格分隔。
样例输入:
2 1
7
1 2
10 9
2 5
10 8 6 4 1
5 4
1 1 1 1
0 0
样例输出:
3 7
10 10
8 18
0 0

我的程序错了!!!
程序代码:
#include<cstdio>
#include<cstring>
#define min(a,b)((a)<(b)?(a):(b))

const int INF=2000000000;
const int maxm=30+1;
const int maxn=100+1;

int n,m;
int a[maxm];
int f[maxm][maxn];
int g[maxm][maxn];

void init()
{
     memset(a,0,sizeof(a));
     memset(f,0,sizeof(f));
     for (int i=1;i<=m;i++) scanf("%d",&a[i]);
}


void doit()
{
     for (int i=0;i<=m;i++) f[i][0]=INF;
     for (int i=1;i<=m;i++)
       for (int j=1;j<=n;j++)
         {
             f[i][j]=f[i-1][j];
             for (int k=1;k<=j;k++)
             {
                 int p=min(f[i-1][k-1],a[i]/(j-k+1));
                 if (p>f[i][j]) f[i][j]=p;
             }
         }
}

void ouit()
{
     if (f[m][n]==0) g[m][n]=0;
     else
     { 
         memset(g,127,sizeof(g));
         g[0][0]=0;
         for (int i=1;i<=m;i++)
         {
             int v=a[i];
             int w=a[i]/f[m][n];
             
             for (int j=w;j>=n;j--)
               g[i][j]=min(g[i-1][j],g[i-1][j-w]+v );
         }
     }
     printf("%d %d\n",f[m][n],g[m][n]);
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while (scanf("%d%d",&n,&m),n,m)
    {
          init();
          doit();
          ouit();
    }
    return 0;
}
搜索更多相关主题的帖子: 一个人 
2011-05-31 16:44
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
给点提示亦可以啊
2011-06-03 13:25
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
能不能解释下思路
2011-06-05 13:10
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
输出为神马只有一个?
2011-06-10 13:30
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
http://
上这个网输入题号10163,点击题目栏,在它弹出框的左框(input框)输入你想要测的数据,点击上传,就可以得到标准答案。
有个弊端就是如果想换个输入数据,更换后要点击两次上传。
2011-06-10 13:38
快速回复:求解uva 10163 一道DP题ACM高手来
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018562 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved