游客 注册 | 登录
中文 | En

2524 - SF

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 32 MB

现有一条单向公路，在路的一侧种有N（2<=N<=25）颗特殊花种（SF），由于天气原因，Tom只有h小时(1<=h<=16)的时间收集SF的种子，这是因为SF种子被雨淋后将失去研究价值。现在，Tom位于第1株SF的位置，他可以采摘任意一株SF的种子。从第i株SF到达第i+1株的位置，需要花费的时间单元个数为t（此处时间单元为5分钟），即表示花费时间Ti=5*t（其中i=0..n-1,0<Ti<=960,如t=4，T5=t*5=20,表示从第4株SF到达第5株SF需要花费20分钟）。Tom可有选择地收集途径过程SF的种子，但由于收集难度，每5分钟，他只能收集Fi颗SF的种子（很苦哈）。天气越来较差，使得Tom在收集SF的种子过程中会掉落部分种子（更苦了，收集效率还下降），假设Tom每1个时间单元掉落个数增加Di（掉落的没有收集价值，如果某SF的Fi小于等于Di,5分钟后，每一时间单元可收集种子个数将为0）。

Tom为了使损失最小，尽量多地收集种子，Tom需要进行简单的规划。现在请你帮他设计一程序，求取在SF种子收集数最大的前提下，Tom在每个SF停留的时间。

注意：在每个SF停留的时间，均为5的倍数。SF种子满足方案要求，即可认为种子数目极多。

题目输入

每组数据第1行为N，h，之后的3行为i处收集SF种子的详细情况。

第(1）行为每一个时间单元,可收集第i株SF种子数Fi（i=1..N）,

第(2) 行为Tom在收集第i株SF种子的过程中，每一个时间单元掉落SF种子个数的增加量Di（i=1..N）,

第(3) 行为Tom从第i株SF走到第i+1株所需要花费的时间（i=1..N-1）。

数据的输入以0结束。 


<br />

题目输出

每组数据输出2行，

第1行输出在Tom需在每个SF停留的时间，

第2行输出Tom可收集到最大种子数。

如果方案存在，尽可能地多的停留在第1株SF处(人懒哈)，如果还有方案与其平局，需尽可能地停留在第2株SF处，依次类推。

输入/输出样例

输入格式

2 1
10 1
2 5
2

4 4
10 15 20 17
0 3 4 3
1 2 3

4 4
10 15 50 30
0 3 4 3
1 2 3

0

输出格式

45, 5
Number of seeds collected: 31
240, 0, 0, 0
Number of seeds collected: 480
115, 10, 50, 35
Number of seeds collected: 724

C++解答

#include<cstdio>
#include<cstring>
using namespace std;
int fi[28],di[28],ti[28],f[28];
int Enum(int end,int h,int *t){
    int left=h,max=0,v=1,sum=0,i;
    for(i=1;i<end;i++)  {left-=5*ti[i];f[i]=fi[i];}
    f[end]=fi[end];
    while(left>0){
        max=0;
        for(i=1;i<=end;i++)
            if(f[i]>max)  {max=f[i];v=i;}
            if(!max) break;
            f[v]-=di[v];
            sum+=max;
            t[v]+=5;
            left-=5;
    }
    t[1]+=left;
return sum;
}
int main(){
	int n,h,i,j,max=0,m,ans[28],t[28];
    while(~scanf("%d",&n)&&n)
    {
    max=-1;
    scanf("%d",&h);h*=60;
    for(i=1;i<=n;i++) scanf("%d",&fi[i]);
    for(i=1;i<=n;i++) scanf("%d",&di[i]);
    for(i=1;i<n;i++) scanf("%d",&ti[i]);
    for(i=1;i<=n;i++){
         memset(t,0,sizeof(t));
         m=Enum(i,h,t);
        if(m>max) {max=m;for(j=1;j<=n;j++) ans[j]=t[j];}
    }
    for(i=1;i<n;i++)
        printf("%d, ",ans[i]);
    printf("%d\nNumber of seeds collected: %d\n",ans[n],max);
  }
}
请先登陆