In a typical assembly line, machines are connected one by one. The first machine's output product will be the second machine's raw material. To simplify the problem, we put all machines into a two-dimension shelf. Every machine occupied exactly one grid and has two input ports and only one output port. One input port can get material from only one machine.
Pipes will be used to connect between these machines. There are two kinds of pipes : 'I' kind and 'L' kind. We should notice that the 'I' kind pipe can be linked one by one. Each pipe will also occupied one grid.
In Bob's factory, each machine will get raw materials from zero, one or two other machines. Some machines don't need any input materials, but any machine must have an output. Machines are coded by numbers from 1 to n. The output of the machines with greater code can be the input of the machines with less code. The machine NO.1's output product will be the final product, and will not be any other machine's input. Bob's factory has a shelf with infinite height, but finite width. He will give you the dependency relationship of these machines, and want you to arrange these machines and pipes so that he can minimize the width of the shelf.
Here's an example for you to help understand :
Products will falling from higher machine to lower machine through the pipes. Here, machine 1 gets materials from machine 2 and machine 3. The whole width of this system is 2.
For each case, the first line will be an integer n indicates the number of the machines (2≤ n≤ 10000). The following line will include n-1 numbers. The i-th number ai means that the output of machine i+1 will be the input of machine ai (ai≤ i). The same code will be appeared at most twice. Notice machine 1's output will be the final output, and won't be any machine's input.
For each case, we need exactly one integer as output, which is the minimal width of the shelf.
Case 1 is the example. Case 2:
题意：有n个机器，每个机器有两个入口，一个出口，上一个机器的产物可以作为下一个机器的原料，两个机器之间可以用'L'型和'I'型的管子相连，问所有的机器连好之后，最小的宽度位多少；
思路：把这个图倒过来看就是一颗二叉树，然后有一种做法可以用树形dp，但是本人太弱dp不是很会，讲一下用记忆化递归怎么做；其实这题用dp用递归都需要找到正确的策略，我们仔细观察可以发现，如果一个点有两个子节点（倒过来看），那么这个点和它的子节点的宽度会在原来的基础上加一，如果只有一个子节点，那么这个点和她子节点的宽度等于它子节点和它所有孙子节点的宽度，如果它没有子节点，所名为叶子节点，宽度即为1；
AC代码：
#include<iostream> #include<cstdio> #include<stack> #include<algorithm> #include<cstring> #include<vector> #define maxn 10005 using namespace std; vector<int> arr[10005];//arr存子节点 int n; int dp[10005]; int dfs(int x) { if(dp[x]) return dp[x]; if(arr[x].size()==0) dp[x]=1; else if(arr[x].size()==1) dp[x]=dfs(arr[x][0]); else if(arr[x].size()==2)//两个节点的时候，宽度会加一 dp[x]=min(max(dfs(arr[x][0])+1,dfs(arr[x][1])),max(dfs(arr[x][0]),dfs(arr[x][1])+1)); return dp[x]; } int main() { while(~scanf("%d",&n)) { int x; for(int i=0;i<=n;i++) arr[i].clear(); memset(dp,0,sizeof(dp)); for(int i=2;i<=n;i++) { scanf("%d",&x); arr[x].push_back(i); } printf("%d\n",dfs(1)); } return 0; }
