首页 > 代码库 > HDU 4340

HDU 4340

2024-08-06 20:33:52   215人阅读

好题一道啦。做这题时，抓住两个问题：一、给某点染色时，其连通的点是否已有一点以全部代价染色。二、该点染什么颜色。

嗯。第二个问题很容易，但第一个问题不容易了。我一开始就考虑祖父子三层结点的关系，认为在父结点时，要么子结点已染色，要么父结点已染色%#……*&￥%#……

很复杂。。。。

这是条件定得过于严格了，所以走不通。看了题解后，发现，可以把状态条件设得宽一点。

设dp[rt][0][0]为以rt为根的子树内，rt染0颜色，与其连通的块（同色，在子树内的）中，没有一个节点是以全部代价染色的，即没有入口点。

dp[rt][0][1]则为以rt为根的子树内，rt染0颜色，与其连通的块（同色，在子树内的）中，存在一个节点是以全部代价染色的。感觉这个存在实现设得妙，只要存在就可以，条件放宽了许多。

对于dp[r][1][0],dp[r][1][1]有同样的定义。

于是dp[rt][0][0]=sum(min(dp[son][0][0],dp[son][1][1]))+costrt/2;

dp[rt][0][1]=sum(min(dp[son][0][0],dp[son][1][1]))+min(costrt,costrt/2+min(dp[son][0][1]-min(dp[son][0][0],dp[son][1][1]))).解释一下min(dp[son][0][1]-min(dp[son][0][0],dp[son][1][1])。这是把子结点以根的子树状态转化为dp[rt][0][1]的最小代价，其中min(dp[son][0][0],dp[son][1][1])与方程开始的min(dp[son][0][0],dp[son][1][1])是一致的，因而又是一个巧妙的地方。

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #define N 110 7  8 using namespace std; 9 int costA[N],costB[N];10 11 int dp[N][2][2];12 13 struct edge{14     int u,v;15     int next;16 }Edge[N*2];17 int n,tot;18 int head[N];19 20 void addedge(int u,int v){21     Edge[tot].u=u;22     Edge[tot].v=v;23     Edge[tot].next=head[u];24     head[u]=tot++;25 }26 27 void dfs(int now,int pre){28     bool leaf=true;29     int sum0=0,sum1=0;30     int CA=(1<<30),CB=(1<<30);31     for(int e=head[now];e!=-1;e=Edge[e].next){32         int v=Edge[e].v;33         if(v!=pre){34             leaf=false;35             dfs(v,now);36             sum0+=min(dp[v][0][0],dp[v][1][1]);37             sum1+=min(dp[v][1][0],dp[v][0][1]);38             CA=min(CA,dp[v][0][1]-min(dp[v][0][0],dp[v][1][1])+costA[now]/2);39             CB=min(CB,dp[v][1][1]-min(dp[v][1][0],dp[v][0][1])+costB[now]/2);40         }41     }42     if(leaf){43         dp[now][0][0]=costA[now]/2;44         dp[now][0][1]=costA[now];45         dp[now][1][0]=costB[now]/2;46         dp[now][1][1]=costB[now];47     }48     else{49         dp[now][0][0]=sum0+costA[now]/2;50         dp[now][0][1]=sum0+min(costA[now],CA);51         dp[now][1][0]=sum1+costB[now]/2;52         dp[now][1][1]=sum1+min(costB[now],CB);53     }54 }55 56 int main(){57     int u,v;58     while(scanf("%d",&n)!=EOF){59         tot=0;60         memset(head,-1,sizeof(head));61         for(int i=1;i<=n;i++)62         scanf("%d",&costA[i]);63         for(int i=1;i<=n;i++)64         scanf("%d",&costB[i]);65         for(int i=1;i<n;i++){66             scanf("%d%d",&u,&v);67             addedge(u,v);68             addedge(v,u);69         }70         dfs(1,0);71         printf("%d\n",min(dp[1][0][1],dp[1][1][1]));72     }73     return 0;74 }
View Code

 

HDU 4340


联系
我们