gone fishing.txt

ACM里面一道题目

#include<iostream>

using namespace std;

int main()

{

       int i,j,k,g,n,h,ans,tot,tt=0,f[32],d[32],t[32],now[32],tnow[32],times[32];

       while (scanf("%d",&n),n)

       {

              if (tt++)

                     printf("\n");

              scanf("%d",&h);

              h*=12;

              for (i=0;i<n;++i)

              {

                     scanf("%d",&f[i]);

                     now[i]=f[i];

              }

              for (i=0;i<n;++i)

                     scanf("%d",&d[i]);

              for (i=0;i<n-1;++i)

                     scanf("%d",&t[i]);

              memset(times,0,sizeof(times));

              for (ans=i=0;i<n&&h>0;++i)

              {

                     for (j=0;j<i;++j)

                            now[j]=f[j];

                     memset(tnow,0,sizeof(tnow));

                     for (tot=k=0;k<h;++k)

                     {

                            for (g=0,j=1;j<=i;++j)

                                   if (now[j]>now[g])

                                          g=j;

                            tot+=now[g];

                            now[g]-=d[g];

                            if (now[g]<0)

                                   now[g]=0;

                            ++tnow[g];

                     }

                     if (tot>ans)

                     {

                            ans=tot;

                            for (j=0;j<n;++j)

                                   times[j]=tnow[j];

                     }

                     else if (tot==ans)

                     {

                            for (j=0;j<n;++j)

                                   if (tnow[j]!=times[j])

                                          break;

                            if (j<n&&tnow[j]>times[j])

                                   for (g=j;g<n;++g)

                                          times[g]=tnow[g];

                     }

                     h-=t[i];

              }

              for (i=0;i<n-1;++i)

                     printf("%d, ",times[i]*5);

              printf("%d\nNumber of fish expected: %d\n",times[n-1]*5,ans);

       }

       return 0;

}










#include<iostream>
using namespace std;
int n,h;
int finaltime[26][26]={0};//纪录输出前i个鱼池情况 
int timeeve[26]={0};//纪录每次剩余的时间 
int findmax(int *f,int *d,int i)
{
    int temp=-1;
    int pos=1;
    int j;
    for(j=1;j<=i;j++)
    {
        
        if(temp<f[j]) {temp=f[j];pos=j;}
    }
    return pos;
    
}
int maxfish(int *p,int *q,int *t,int i)
{
    
    int j;
    for(j=1;j<=i;j++)
    {finaltime[i][j]=0;}
    int f[26]={0};
    int d[26]={0};
    for(j=1;j<=i;j++){f[j]=p[j];d[j]=q[j];}
    int time=h/5;
    for(j=i-1;j>=1;j--){time-=t[j];}
    int max_fish=0;
    for(;time>0;time--)
    {
        int temp=findmax(f,d,i);
        if(f[temp]<=0) break;
        max_fish+=f[temp];
        finaltime[i][temp]+=5;
        f[temp]-=d[temp];
    } 
    timeeve[i]=time;
    return max_fish;
} 
int main()
{
    
    while(cin>>n&&n!=0)
    {
        cin>>h;
        h*=60;
        int f[26]={0};
        int d[26]={0};
        int t[25]={0};
        int jilu[26]={0};
        int i;
        
        
         
        for(i=1;i<=n;i++){cin>>f[i];}
        for(i=1;i<=n;i++){cin>>d[i];}
        for(i=1;i<=n-1;i++){cin>>t[i];}
        
        
        
        
        for(i=1;i<=n;i++)
        {
            jilu[i]=maxfish(f,d,t,i);
        }
       
        
        int j,pos;
        int temp=-1;
        for(i=1;i<=n;i++)
        {
            
            if(temp<jilu[i]) {temp=jilu[i];pos=i;}
        }
       
        cout<<finaltime[pos][1]+timeeve[pos]*5<<", ";
        for(i=2;i<=n-1;i++)
        {cout<<finaltime[pos][i]<<", ";}
        cout<<finaltime[pos][n]<<endl;
        cout<<"Number of fish expected: ";
        cout<<jilu[pos]<<endl;
        cout<<endl;
        
    }
}
 





#include "stdafx.h"

#include "iostream.h"

 

int main(int argc, char* argv[])

{

       int n,h,k,fi[25],di[25],ti[25],first,i,j,temp_fi[25],max_fi,max,temp_max,need_h,temp_h,temp_time[25],time[25];

       first=0;

       while((cin>>n)&&(n!=0))

       {

              if(first==0)

                     first=1;

              else

                     cout<<endl;

              cin>>h;

              for(i=0;i<n;i++)

                     cin>>fi[i];

              for(i=0;i<n;i++)

                     cin>>di[i];

              for(i=1;i<n;i++)

                     cin>>ti[i];

              ti[0]=0;

              h=h*12;

              max=-1;

              temp_max=0;

              max_fi=-1;

              need_h=0;

              for(i=0;i<n;i++)

                     temp_time[i]=0;

              for(i=0;i<n;i++)

              {

                     temp_h=h;

                     temp_max=0;

                     for(j=0;j<=i;j++)

                     {

                            temp_fi[j]=fi[j];

                            temp_time[j]=0;

                     }

                     need_h=need_h+ti[i];

                     temp_h=h-need_h;

                     if(temp_h<=0)

                            break;

                     while(temp_h>0)

                     {

                            max_fi=-1;

                            for(j=0;j<=i;j++)

                            {

                                   if(max_fi<temp_fi[j])

                                   {

                                          max_fi=temp_fi[j];

                                          k=j;

                                   }

                            }

                            if(temp_fi[k]<=di[k])

                                   temp_fi[k]=0;

                            else

                                   temp_fi[k]=temp_fi[k]-di[k];

                            temp_max=temp_max+max_fi;

                            temp_time[k]++;

                            temp_h--;

                     }

                     if(temp_max>max)

                     {

                            max=temp_max;

                            for(j=0;j<n;j++)

                                   time[j]=temp_time[j];

                     }

              }

              for(j=0;j<n;j++)

              {

                     cout<<time[j]*5;

                     if(j!=n-1)

                            cout<<", ";

              }

              cout<<endl;

              cout<<"Number of fish expected: "<<max<<endl;

       }

       

       return 0;

}