P7366 [CTSC2002]月亮森林

bluebayou · 2023-02-28 22:49:57 · 题解

首先可以知道，第二棵和以后的树，越早开始生长越好。

当M棵树种齐后，只需要补齐所有的树和第一棵树的差距就可以了，最终天数只需要加上\sum_{i=2}^{m}H_1-H_i。

在第一棵树还没结种子时，只能给第一棵树施肥， 因此无脑施肥到第一棵树结第一颗种子。

但是可以很明显地观察到

如果再给第一棵树施肥来获取第二颗种子，实际上最好情况下仅仅是让第三棵和以后的树早一天开始生长。

那么这早的一天为了弥补第一棵树多生长的1单位长度而没用了，第二棵树反倒落下1单位长度。

因此，第一棵树结第一颗种子后，就把它晾在那吧（逃

还有一个显而易见的结论：

如果一棵树已经结了第二颗种子,或自然生长1单位长度后要第二颗种子，那么它就再也不用被施肥了。

因为如果给它施肥是浪费，还不如给更矮的树施肥催种子。

那么施肥的时间可以改为第二天收种子前，立即见效。

在此前提下，我们有一个贪心策略：给距离结种子最近的树施肥。

即：设当前有n棵树，则选择H_i<HP_2且\lfloor \frac{(H_i\geq HP_1?HP_2:HP_1)-H_i}{2}\rfloor最大值对应的第i棵树施肥。

该贪心策略在大部分情况下是正确的，并能通过本题。

至于为什么是“大部分”,详见 Hack

示例程序

该代码由提交向UVa10833的WA代码适当修改而成，在该题能AC（大雾

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,Hp[5],H[100],State[100];
int main(){
        cin>>Hp[0]>>Hp[1]>>m;n=1;
        Hp[2]=inf;
        for(int i=0;i<m;i++)
            {H[i]=0;State[i]=0;}
        int ans=0;
        while(n<m){
            ans++;
            int tn=n;
            for(int i=0;i<tn;i++){//tree grow,seed produce and plant
                H[i]++;
                if(H[i]>=Hp[State[i]])
                    {State[i]++;n++;}
            }
            int pouron;//Try to pour magic water for tomorrow
            if(tn==1)pouron=0;
            else{
                int i,j;
                for(i=1;i<tn;i++)
                    if(State[i]<2)break;
                for(j=i;j<tn;j++)
                    if(State[j]==0)break;
                if(j>=tn||State[j]!=0)pouron=i;
                else pouron=((Hp[1]-H[i])/2<(Hp[0]-H[j])/2)?i:j;
            }
            H[pouron]++;
            if(H[pouron]>=Hp[State[pouron]])
                {State[pouron]++;n++;}
        }
        for(int i=1;i<m;i++)
            ans+=H[0]-H[i];
        cout<<ans<<endl;
    return 0;
}

Hack

上述数据都不在官方数据中，或官方实际上不知道这些数据的存在，或者官方的标准程序与示例程序实现相似或相同。贪心算法对这些数据无效，并且目前没有已知有效算法能够兼顾这些数据。

另附UVa10833 AC Code:（暴力法，修改后在该题成绩60）

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int m,Hp[5],H[20],State[20];

int dfs(int cnt,int cur){
    if(cnt>=m){
        int ans=0;
        for(int i=1;i<m;i++)
            ans+=H[0]-H[i];
        return ans;
    }
    int ans=inf,newcnt=cnt;
    for(int i=0;i<cnt;i++){
        H[i]++;
        while(H[i]>=Hp[State[i]])
            {State[i]++;newcnt++;}
    }
    if(cur+1<cnt&&State[cur+1]<2){
        int hh=H[cur+1],ss=State[cur+1],cc=newcnt;
        H[cur+1]++;
        while(H[cur+1]>=Hp[State[cur+1]])
            {State[cur+1]++;newcnt++;}
        ans=min(ans,dfs(newcnt,cur+1));
        H[cur+1]=hh;State[cur+1]=ss;newcnt=cc;
    }
    {
        int pouron;//Try to pour magic water for tomorrow
        if(cnt==1)pouron=0;
        else{
            int i,j;
            for(i=1;i<cnt;i++)
                if(State[i]<2)break;
            for(j=i;j<cnt;j++)
                if(State[j]==0)break;
            if(j>=cnt||State[j]!=0)pouron=i;
            else pouron=((Hp[1]-H[i])/2<(Hp[0]-H[j])/2)?i:j;
        }
        int hh=H[pouron],ss=State[pouron],cc=newcnt;
        H[pouron]++;
        if(H[pouron]>=Hp[State[pouron]])
            {State[pouron]++;newcnt++;}
        ans=min(ans,dfs(newcnt,pouron));
        H[pouron]=hh;State[pouron]=ss;newcnt=cc;
    }
    for(int i=0;i<cnt;i++){
        H[i]--;
        while(H[i]<Hp[State[i]-1])
            State[i]--;
    }
    return 1+ans;
}

int main(){int o,_o=1;
    for(cin>>o;_o<=o;_o++){
        cin>>Hp[0]>>Hp[1]>>m;
        Hp[2]=inf;
        for(int i=0;i<m;i++)
            {H[i]=0;State[i]=0;}
        cout<<"Case "<<_o<<": ";
        if(m==1)cout<<1<<endl;
        else cout<<dfs(1,0)<<endl;
    }
    return 0;
}