这一节做得很郁闷，题目以动态规划为主，而本人的动规很弱，做的很勉强。。。
Longest Prefix
问题描述：
给定一堆短字符串，和一条长字符串，求用短字符串组成的长字符串的最长前缀长度。
分析：
看完题目首先想到的是DFS，写完提交上去后到第三组数据就超时了。。。看了别人的题解，原来要用动规，用dp[i]表示当前能拼到的最长前缀，然后在短字符里面寻找最长的能和长字符串继续匹配的，然后i+1！本来想第一次试试Hash，但写到一半觉得函数写得不够好，先记住了，有空了用Hash优化一遍。
Cow Pedigrees
问题描述：
给定一颗树的节点数和度，问其能构成多少种不同的数。
分析：
这题虽然明知道要用动规，但想了一下午都没想出状态转移方程来，囧~。看了网上的官方题解，一颗树显然要由一颗小树（根节点）构成，可以是左子树，也可以是右子树，分三种情况，左长，右长，左右同长。状态转移方程如下：
table[i][j] += smalltrees[i-2][k]*table[i-1][j-1-k];
// 左子树深度小于i-1，右子树深度为i-1
table[i][j] += table[i-1][k]*smalltrees[i-2][j-1-k];
// 左子树深度为i-1，右子树深度小于i-1
table[i][j] += table[i-1][k]*table[i-1][j-1-k];
// 左右子树深度都为i-1
Zero Sum
问题描述：
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。
分析：
这题在培训的时候讲过，创建一个字符串“1 2 3 4 5 6 7 8 9 ”数字间隔着空格，然后在空格位置枚举写入‘ ’，‘+’，‘-’递归（其实也就是简单的DFS）。把字符串转成数字运算，若结果为0则输出。
Money Systems
问题描述：
给出一套钱币的面值，求组成某数N有多少种方案。
分析：
这是个简单的动规，用dp[ i ] [ j ]表示仅用前i种钱币拼成j的方案数，那么仅用前i-1种钱币拼成j的方案dp[i-1][j]也满足，如果用了一枚面值为i的钱币，则dp[i][j]+=dp[i-1][j-v[i]]其中v[i]为i的面值，同理，用了两枚dp[i][j]+=dp[i-1][j-2*v[i]]，一直到j-k*v[i]<=0为止。
注意，当j可以被v[i]整除时，dp[i][j]++;初始化dp[1][k*v[1]]=1,(k*v[i]<=N)
状态转移方程为：
dp[i][j] =∑dp[i-1][j-k*v[i]];（k=1..j/v[i]）
Controlling Companies
问题描述：
有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。如果至少满足了以下三个条件之一，公司A就可以控制公司B了：
1.公司A = 公司B。
2.公司A拥有大于50%的公司B的股票。
3.公司A控制K(K >= 1)个公司，记为C1, ..., CK，每个公司Ci拥有xi%的公司B的股票，并且x1+ .... + xK > 50%。
给你一个表，每行包括三个数(i,j,p)；表明公司i享有公司j的p%的股票。计算所有的数对(h,s)，表明公司h控制公司s。至多有100个公司。
写一个程序读入三对数(i,j,p)，i,j和p是都在范围(1..100)的正整数，并且找出所有的数对(h,s)，使得公司h控制公司s。
分析：
这题似乎很麻烦，当你控制了一家新公司后，新公司又有可能控制着另一家公司，构成一层接一层的迭代关系。。。刚开始用DFS的时候思路就比较混乱，结果只通过了前六个测试，而且效率很低，后来细细分析了一下，其实这有点类似图的结构，题目给出的表可以看做邻接矩阵。问题就转化为，以某点作为原点出发，如果原点到某点s的距离超过50，那么把s纳入原点所在集合P，找与s距离超过50的点，再次纳入P，不断更新原点到这些点的距离。最后列出所有到原点距离超过50的点。
int Own[101][101]=
{0};
int current[101];
bool visit[101],flag;
int N,MAX=0,MIN=1<<30;
void Search(int n)
{ int i,j;
for(j=MIN;j<=MAX;j++)
{ current[j]+=Own[n][j];
if(current[j]>50&&!visit[j])
{ visit[j]=true;
Search(j);
}
}
}
int main()
{ memset(visit,false,sizeof(visit));
fin>>N;
int t=N,i,j,p;
while(t--)
{ fin>>i>>j>>p;
Own[i][j]+=p;
if(i>MAX)
MAX=i;
if(i<MIN)
MIN=i;
if(j<MIN)
MIN=j;
if(j>MAX)
MAX=j;
}
for(i=MIN;i<=MAX;i++)
{ memset(current,0,sizeof(current));
memset(visit,false,sizeof(visit));
Search(i);
for(j=MIN;j<=MAX;j++)
if(current[j]>50&&j!=i)
fout<<i<<" "<<j<<endl;
}
return 0;
}