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++
补充：软件开发 , C++ ,
