Posted on 2012-04-06 08:13
C小加 閱讀(1880)
評論(3) 編輯 收藏 引用 所屬分類:
解題報告
第一次WA，發(fā)現(xiàn)輸出格式不對，改掉。
第二次WA，對結(jié)果相等的情況沒有考慮，改掉。
第三次AC。
題意和題解見黑書P13。
需要注意的是要枚舉從第一個湖走到最后一個湖的每一種情況，對結(jié)果相等這種情況做特殊處理。
#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)//找魚的數(shù)量最多的湖
{
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)//細節(jié)，答案相等時做的處理。
{
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;
}