這一節做得很郁悶，題目以動態規劃為主，而本人的動規很弱，做的很勉強。。。
Longest Prefix
問題描述：
給定一堆短字符串，和一條長字符串，求用短字符串組成的長字符串的最長前綴長度。
分析：
看完題目首先想到的是DFS，寫完提交上去后到第三組數據就超時了。。。看了別人的題解，原來要用動規，用dp[i]表示當前能拼到的最長前綴，然后在短字符里面尋找最長的能和長字符串繼續匹配的，然后i+1！本來想第一次試試Hash，但寫到一半覺得函數寫得不夠好，先記住了，有空了用Hash優化一遍。
Cow Pedigrees
問題描述：
給定一顆樹的節點數和度，問其能構成多少種不同的數。
分析：
這題雖然明知道要用動規，但想了一下午都沒想出狀態轉移方程來，囧~?？戳司W上的官方題解，一顆樹顯然要由一顆小樹（根節點）構成，可以是左子樹，也可以是右子樹，分三種情況，左長，右長，左右同長。狀態轉移方程如下：
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;
}