//按照lrj的书上的算法做的，减掉路程的时间后，每次选最大的钓鱼量

#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

int main(){
    ifstream cin("tmp.txt");
    int h,n,f[26],d[26],t[26];
    while(cin>>n&&n!=0){
        
        cin>>h;
        h*=12;
        int i,j,k;
        for(i=0;i<n;i++){
            cin>>f[i];
        }
        for(i=0;i<n;i++){
            cin>>d[i];
        }
        t[0]=0;
        for(i=1;i<n;i++){
            cin>>t[i];
        }
        int res[26]={0};
        int max_s=0;
        for(j=0;j<=n-1;j++){
            int ff[26];
            for(i=0;i<26;i++){
                ff[i]=f[i];
            }    
           
            h-=t[j];
            if(h<=0)break;
               
            int count[26]={0};
            int s=0;
            int pos;   
            for(i=0;i<h;i++){
                int max_=ff[0];     //找最大元素
                pos=0; 
                for(k=0;k<=j;k++){
                    if(ff[k]>max_){
                        max_=ff[k];
                        pos=k;
                    }
                }        
                    
                s+=ff[pos];
                count[pos]++;    //计数
                ff[pos]-=d[pos];
                if(ff[pos]<=0)ff[pos]=0;
            }
            if(max_s<s){
                max_s=s;
                for(i=0;i<n;i++){
                    res[i]=count[i];
                }
            }        
        }    
        for(i=0;i<n;i++){
            cout<<res[i]*5;
            if(i==n-1)cout<<endl;
            else cout<<", ";
        }
        cout<<"Number of fish expected: "<<max_s<<endl;
        cout<<endl;
       
    }
    system("pause");
    return 0;
}        
                
            
                           
        
        

• 应该不能贪心，要用dp的 (56) hawk 2005-05-12 10:34:25
  • 我是在t+x的时候在重新贪心，这样枚举他的最后目的地n次，每次都重新贪心法算一次，o(n^2) (60) tianya 2005-05-12 11:59:12
  • 可以贪心的(lrj的书上有) (60) windbells 2005-05-12 12:01:01
    • 确实可以贪心，但应该说是基于枚举的贪心 (0) TN 2005-05-12 12:04:37
      • 这个O(mnlogn)贪心的效率怎么样？我用STL的堆写的好像很慢 (0) frkstyc 2005-05-12 12:17:27
        • 我都是自己写heap (0) TN 2005-05-12 12:22:13
          • 建堆的时候每步插入快还是整体建堆快？ (26) frkstyc 2005-05-12 12:33:37
        • 效率应该比DP高吧 (0) TN 2005-05-12 12:22:36
        • 整1000 submissions了 (0) frkstyc 2005-05-12 12:31:21
      • 只能说在某一步贪心了，整体算法不该说成贪心吧 (0) hawk 2005-05-12 12:28:42