UVA 12452

簡單樹形DP

昨天做這道題一直RE，最後在隊友幫助下手寫棧過了

今天再看昨天的代碼，發現自己確實寫搓了，在每次dfs中都要開10000的數組不爆才怪.....換種寫法就可以了

代碼能力太渣沒辦法，繼續加油！

[cpp]
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<algorithm>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<vector>  
#include<map>  
#include<ctime>  
#include<set>  
#include<string>  
#define N 20010  
using namespace std; 
 
struct Edge{ 
    int v,next; 
}edge[N*2]; 
 
int head[N]; 
int n,cnt; 
int dp[N][2]; 
void init(){ 
    memset(head,-1,sizeof(head)); 
    memset(dp,0,sizeof(dp)); 
    cnt=0; 
} 
 
void addedge(int u,int v){ 
    edge[cnt].v=v; 
    edge[cnt].next=head[u]; 
    head[u]=cnt++; 
 
    edge[cnt].v=u; 
    edge[cnt].next=head[v]; 
    head[v]=cnt++; 
} 
 
void dfs(int u,int fa){ 
    int sum=0; 
    int ans1=0,ans2=0; 
    int a[2],j=0; 
    a[0]=a[1]=1000000000; 
    for(int i=head[u];i!=-1;i=edge[i].next){ 
        int v=edge[i].v; 
        if(v==fa)continue; 
        sum++; 
        dfs(v,u); 
        ans1+=dp[v][0]; 
        ans2+=dp[v][1]; 
        if(a[0]>dp[v][0]-dp[v][1]){ 
            a[1]=a[0]; 
            a[0]=dp[v][0]-dp[v][1]; 
        } 
        else if(a[1]>dp[v][0]-dp[v][1]) a[1]=dp[v][0]-dp[v][1]; 
    } 
    if(sum==0){ 
        dp[u][0]=0; 
        dp[u][1]=100; 
        return ; 
    } 
 
    dp[u][0]=ans2; 
    dp[u][0]=min(dp[u][0],ans1+500);     //all cover  
 
    dp[u][0]=min(dp[u][0],ans2+a[0]+100);  //cover 1  
    if(sum>1) 
        dp[u][0]=min(dp[u][0],ans2+a[0]+a[1]+175); //cover 2  
 
    if(fa==-1)return; 
 
    dp[u][1]=ans2+100; 
    dp[u][1]=min(dp[u][1],ans1+500);    //all cover  
    dp[u][1]=min(dp[u][1],ans2+a[0]+175); 
} 
 
int main(){ 
    int t,T,u,v,i; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d",&n); 
        init(); 
        for(i=0;i<n-1;i++){ 
            scanf("%d %d",&u,&v); 
            addedge(u,v); 
        } 
        dfs(0,-1); 
        printf("$%d\n",dp[0][0]); 
    } 
    return 0; 
} 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
#include<set>
#include<string>
#define N 20010
using namespace std;

struct Edge{
    int v,next;
}edge[N*2];

int head[N];
int n,cnt;
int dp[N][2];
void init(){
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
    cnt=0;
}

void addedge(int u,int v){
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void dfs(int u,int fa){
    int sum=0;
    int ans1=0,ans2=0;
    int a[2],j=0;
    a[0]=a[1]=1000000000;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)continue;
        sum++;
        dfs(v,u);
        ans1+=dp[v][0];
        ans2+=dp[v][1];
        if(a[0]>dp[v][0]-dp[v][1]){
            a[1]=a[0];
            a[0]=dp[v][0]-dp[v][1];
        }
        else if(a[1]>dp[v][0]-dp[v][1]) a[1]=dp[v][0]-dp[v][1];
    }
    if(sum==0){
        dp[u][0]=0;
        dp[u][1]=100;
        return ;
    }

    dp[u][0]=ans2;
    dp[u][0]=min(dp[u][0],ans1+500);     //all cover

    dp[u][0]=min(dp[u][0],ans2+a[0]+100);  //cover 1
    if(sum>1)
        dp[u][0]=min(dp[u][0],ans2+a[0]+a[1]+175); //cover 2

    if(fa==-1)return;

    dp[u][1]=ans2+100;
    dp[u][1]=min(dp[u][1],ans1+500);    //all cover
    dp[u][1]=min(dp[u][1],ans2+a[0]+175);
}

int main(){
    int t,T,u,v,i;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d",&n);
        init();
        for(i=0;i<n-1;i++){
            scanf("%d %d",&u,&v);
            addedge(u,v);
        }
        dfs(0,-1);
        printf("$%d\n",dp[0][0]);
    }
    return 0;
}

手寫棧的版本

[cpp]
//#pragma comment(linker,"/STACK:1024000000,1024000000")  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include<stack>  
#define N 100010  
 
using namespace std; 
 
struct Edge{ 
    int v,next; 
}edge[N*2]; 
 
int head[N]; 
int n,cnt; 
int dp[N][2]; 
void init(){ 
    memset(head,-1,sizeof(head)); 
    memset(dp,0,sizeof(dp)); 
    cnt=0; 
} 
 
void addedge(int u,int v){ 
    edge[cnt].v=v; 
    edge[cnt].next=head[u]; 
    head[u]=cnt++; 
 
    edge[cnt].v=u; 
    edge[cnt].next=head[v]; 
    head[v]=cnt++; 
} 
 
void dfs(){ 
 
    stack<pair<int, int> > sta; 
    sta.push(make_pair(0, -1));                //*******  
    bool vis[N]; 
    memset(vis,0,sizeof(vis)); 
    while (!sta.empty()){                         //*******  
        int u = sta.top().first, fa = sta.top().second;      //*******  
         
        if(vis[u]==0){                              //*******  
            for(int i=head[u];i!=-1;i=edge[i].next){ 
                int v=edge[i].v; 
                if(v==fa)continue; 
                sta.push(make_pair(v, u));     //*******  
            } 
            vis[u]=1;                         //*******  
        } 
        if (u != sta.top().first)           //*******  
            continue; 
        sta.pop();                         //*******  
        int sum=0; 
        int ans1=0,ans2=0; 
        for(int i=head[u];i!=-1;i=edge[i].next){ 
            int v=edge[i].v; 
            if(v==fa)continue; 
            sum++; 
            ans1+=dp[v][0]; 
            ans2+=dp[v][1]; 
        } 
        if(sum==0){ 
            dp[u][0]=0; 
            dp[u][1]=100; 
            continue ; 
        } 
        dp[u][0]=ans2; 
        if(sum==1) dp[u][0]=min(dp[u][0],ans1+100); 
        else if(sum==2) dp[u][0]=min(dp[u][0],ans1+175); 
        else dp[u][0]=min(dp[u][0],ans1+500);     //all cover  
 
        int a[N],j=0; 
        if(sum>1){ 
            for(int i=head[u];i!=-1;i=edge[i].next){ 
                int v=edge[i].v; 
                if(v==fa)continue; 
                a[j++]=dp[v][0]-dp[v][1]; 
            } 
            sort(a,a+j); 
            dp[u][0]=min(dp[u][0],ans2+a[0]+100);  //cover 1  
            if(sum>2) 
                dp[u][0]=min(dp[u][0],ans2+a[0]+a[1]+175); //cover 2  
        } 
        if(fa==-1)continue; 
 
        dp[u][1]=ans2+100; 
        if(sum==1) dp[u][1]=min(dp[u][1],ans1+175); 
        else dp[u][1]=min(dp[u][1],ans1+500);    //all cover  
 
        if(sum>1){ 
            dp[u][1]=min(dp[u][1],ans2+a[0]+175); 
        } 
 
    } 
} 
 
 
int main(){ 
    int t,T,u,v,i; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d",&n); 
        init(); 
        for(i=0;i<n-1;i++){ 
            scanf("%d %d",&u,&v); 
            addedge(u,v); 
        } 
        dfs(); 
        printf("$%d\n",dp[0][0]); 
    } 
    return 0; 
}