题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337
题目大意：方块连接，呈树形。每个方块有两种接法，一种接在父块边上，宽度+1,一种接在父块上面，宽度+0。且一个母块最多有2个子块。问全局的宽度最小是多少。
解题思路：
对于一个方块，就两种接法。
设dp[i][0]=0,表示接在父块上面。
dp[i][1]=1，表示接在父块边上。
对于一个父块，如果没有子块，宽度不变。
如果有一个子块，肯定接在上面，加上子块的宽度。
如果有两个子块，则有两种解法，max(左1上2),max(左2上1)， 注意这里两个子块不是加起来，因为只要把管子伸长，让两个子块相互重叠掉一部分宽度，所以取max
那么接这两个子块就得加上这两种解法的较小值。（min）
最后结果是dp[1][1]，和dp[1][0]没关系，因为1块肯定要占一个宽度。
#include "cstdio"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 10005
struct Edge
{
int next,to;
}e[maxn];
int dp[maxn][],head[maxn],tol;
void addedge(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
}
void dfs(int root)
{
int cnt=,l1=,l2=,r1=,r2=;
dp[root][]=,dp[root][]=;
for(int a=head[root];a!=-;a=e[a].next) dfs(e[a].to);
for(int a=head[root];a!=-;a=e[a].next)
{
int t=e[a].to;
if(!cnt) {l1=dp[t][],l2=dp[t][];}
else {r1=dp[t][],r2=dp[t][];}
cnt++;
}
if(!cnt) return;
else if(cnt==) {dp[root][]+=l1;dp[root][]+=l1;}
else
{
int a=max(l1,r2),b=max(l2,r1);
dp[root][]+=min(a,b);dp[root][]+=min(a,b);
}
}
int main()
{
//freopen("in.txt","r",stdin);
int n,u;
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
tol=;
for(int i=;i<=n;i++)
{
scanf("%d",&u);
addedge(u,i);
}
dfs();
printf("%d\n",dp[][]);
}
}
| 3808409 | 2014-10-20 17:37:23 | Accepted | 3805 | C++ | 800 | 468 | Physcal |