[APIO2007 mobiles]树形动态规划

【题目】http://www.oi.bbjy.com/n38c10.aspx

【算法分析】

送分题，树形DP之。

虽然我写的比较复杂，但是第一感觉就这个，没所谓了，反正能AC。

首先风铃只能分布于相邻的两层。

判断以后，设cd为靠上的一层。

然后

F[i][0]表示我下面的都是层数为cd的风铃。

F[i][1]表示我下面的都是层数为cd+1的风铃。

F[i][2]表示我下面的是由cd和cd+1的风铃混合而成，而且满足题目性质。即先是一段cd+1的，然后再是一段cd的。

然后转移一下，就可以了。

【其他】1A

【CODE】

#include #include const int N=101111;
const int INF=1000000000;
int n,cd;
int F[N][3],L[N],R[N],dep[N],v[N];

void input(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
}

void Get_dep(){
     dep[1]=1;
     for (int i=1;i<=n;i++){
         if (L[i]!=-1) dep[L[i]]=dep[i]+1;
         if (R[i]!=-1) dep[R[i]]=dep[i]+1;
     }
}

bool can_same_dep(){
     memset(v,0,sizeof(v));
     int depnum=0;
     for (int i=1;i<=n;i++)
       if (L[i]==-1 || R[i]==-1){
         if (!v[dep[i]]) depnum++;
         v[dep[i]]++;
       }
     if (depnum>2) return false;
     if (depnum<=1) return true;
     for (int i=1;i<=n;i++)
       if (v[i])
         if (v[i+1]){
           cd=i;
           return true;
         }
         else return false;
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x

void dp(){
     int i,j;
     for (i=1;i<=n;i++)
       for (j=0;j<3;j++)
         F[i][j]=INF;
     for (i=1;i<=n;i++)
       if (L[i]==-1 && R[i]==-1)
         if (dep[i]==cd) F[i][0]=0;
                    else F[i][1]=0;
     for (i=n;i>=1;i–)
       if (L[i]!=-1 || R[i]!=-1)
         if (L[i]==-1){
           if (dep[i]==cd){
             F[i][0]=F[R[i]][0];
             F[i][2]=min(F[i][2],F[R[i]][2]+1);
             F[i][2]=min(F[i][2],F[R[i]][1]+1);
           }
           else{
             F[i][1]=F[R[i]][1];
             F[i][2]=min(F[i][2],F[R[i]][2]);
             F[i][2]=min(F[i][2],F[R[i]][0]);
           }
         }
         else if (R[i]==-1){
           if (dep[i]==cd){
             F[i][0]=F[L[i]][0];
             F[i][2]=min(F[i][2],F[L[i]][1]);
             F[i][2]=min(F[i][2],F[L[i]][2]);
           }
           else{
             F[i][1]=F[L[i]][1];
             F[i][2]=min(F[i][2],F[L[i]][2]+1);
             F[i][2]=min(F[i][2],F[L[i]][0]+1);
           }
         }
         else{
           F[i][0]=min(F[i][0],F[L[i]][0]+F[R[i]][0]);
           F[i][1]=min(F[i][1],F[L[i]][1]+F[R[i]][1]);
           int &t=F[i][2];
           t=min(t,F[L[i]][1]+F[R[i]][0]);
           t=min(t,F[L[i]][1]+F[R[i]][2]);
           t=min(t,F[L[i]][2]+F[R[i]][1]+1);
           t=min(t,F[L[i]][2]+F[R[i]][0]);
           t=min(t,F[L[i]][0]+F[R[i]][1]+1);
           t=min(t,F[L[i]][0]+F[R[i]][2]+1);
         }
     int ans=INF;
     ans=min(ans,F[1][0]);
     ans=min(ans,F[1][1]);
     ans=min(ans,F[1][2]);
     if (ans==INF) printf("-1n");
              else printf("%dn",ans);
}

int main(){
    freopen("mobiles.in","r",stdin);
    freopen("mobiles.out","w",stdout);
    input();
    Get_dep();
    if (can_same_dep()) dp();
    else printf("-1n");
}