Posted on 2012-04-06 08:13
C小加 阅读(1852)
评论(3) 编辑 收藏 引用 所属分类:
解题报告
第一次WA，发现输出格式不对，改掉。
第二次WA，对结果相等的情况没有考虑，改掉。
第三次AC。
题意和题解见黑书P13。
需要注意的是要枚举从第一个湖走到最后一个湖的每一种情况，对结果相等这种情况做特殊处理。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXM=30;
int n,h;
int f[MAXM],d[MAXM],t[MAXM];
int each_time[MAXM];
int ans_time[MAXM];
int tf[MAXM];
int ans;
//初始化
void init()
{
memset(each_time,0,sizeof(each_time));
memset(ans_time,0,sizeof(ans_time));
ans=0;
}
//输入
bool input()
{
init();
scanf("%d",&n);
if(0==n) return false;
scanf("%d",&h);
for(int i=0;i<n;++i)
{
scanf("%d",f+i);
}
for(int i=0;i<n;++i)
{
scanf("%d",d+i);
}
for(int i=0;i<n-1;++i)
{
scanf("%d",t+i);
}
return true;
}
void solve(int rem_time,int q)
{
int tans=0;
memset(each_time,0,sizeof(each_time));
memcpy(tf,f,sizeof(f));
for(int i=0;i<rem_time;++i)//找鱼的数量最多的湖
{
int pos=0,max_fish=tf[0];
if(q>0)
for(int j=1;j<=q;++j)
{
if(max_fish<tf[j])
{
max_fish=tf[j];
pos=j;
}
}
++each_time[pos];
tans+=tf[pos];
tf[pos]-=d[pos];
if(tf[pos]<0) tf[pos]=0;
}
if(tans>ans)
{
ans=tans;
memcpy(ans_time,each_time,sizeof(each_time));
}
else if(tans==ans)//细节，答案相等时做的处理。
{
int i;
for(i=0;i<n;++i)
{
if(each_time[i]!=ans_time[i]) break;
}
if(each_time[i]>ans_time[i])
{
memcpy(ans_time,each_time,sizeof(each_time));
}
}
}
void print()
{
printf("%d",ans_time[0]*5);
for(int i=1;i<n;i++)
{
printf(", %d",ans_time[i]*5);
}
printf("\nNumber of fish expected: %d\n\n",ans);
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out2.txt","w",stdout);
while(input())
{
int rem_time=h*60;
rem_time/=5;
solve(rem_time,0);
for(int i=0;i<n-1;++i)//枚举每个湖
{
rem_time-=t[i];
solve(rem_time,i+1);
}
print();
}
return 0;
}