麻涌镇仿做网站/青岛设计优化公司

简单树形DP

昨天做这道题一直RE，最后在队友帮助下手写栈过了

今天再看昨天的代码，发现自己确实写搓了，在每次dfs中都要开10000的数组不爆才怪.....换种写法就可以了

代码能力太渣没办法，继续加油！

#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 coverdp[u][0]=min(dp[u][0],ans2+a[0]+100);  //cover 1if(sum>1)dp[u][0]=min(dp[u][0],ans2+a[0]+a[1]+175); //cover 2if(fa==-1)return;dp[u][1]=ans2+100;dp[u][1]=min(dp[u][1],ans1+500);    //all coverdp[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;
}

手写栈的版本

//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<stack>
#define N 100010using 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 coverint 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 1if(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 coverif(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;
}