石子合并

洛谷P1880 在一個園形操場的四周擺放N堆石子,現要將石子有次序地合并成一堆.規定每次只能選相鄰的2堆合并成新的一堆，并將新的一堆的石子數，記為該次合并的得分。

試設計出1個算法,計算出將N堆石子合并成1堆的最小得分和最大得分.

思路： 定義dp[i][j]$dp[i][j]$ 為合并i到j堆石子所得的最大得分，用數組sum[i]$sum[i]$記錄1~i石子的石子數，通過sum[j]?sum[i?1]$sum[j] - sum[i-1]$計算i~j石子的石子數，枚舉變量k從i~j-1,狀態轉移方程為 dp[i][j]=max(dp[i][k]+dp[k+1][j]+sum[j]?sum[i?1])$dp[i][j] = max(dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])$，求最小值類似。

程序代碼：

Multiplication Puzzle

POJ 1651 The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the PRoduct of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring 10?1?50+50?20?5+10?50?5=500+5000+2500=8000$10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000$

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be 1?50?20+1?20?5+10?1?5=1000+100+50=1150.$1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.$

題意： n個數相乘，每次從中抽取一個數出來與相鄰兩個數相乘，直到抽到只剩兩個數字，第一個數和最后一個數不能抽，求和最小值。

思路： 定義dp[i][j]$dp[i][j]$為從i到j取數后值得最小值，枚舉k?(i,j)$k /epsilon (i, j)$，表示從i到j最后抽取第k個數字， 狀態轉移方程為dp[i][j]=min(dp[i][k]+dp[k][j]+array[i]?array[k]?array[j])$dp[i][j] = min(dp[i][k] + dp[k][j] + array[i] * array[k] * array[j])$。

程序代碼：

Brackets

POJ 2955 We give the following inductive definition of a “regular brackets” sequence:

For instance, all of the following character sequences are regular brackets sequences:

while the following character sequences are not:

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])]$([([]])]$, the longest regular brackets subsequence is [([])]$[([])]$.

題意： 求一字符串括號序列的最大匹配個數。

思路： 定義dp[i][j]$dp[i][j]$為從i到j的最大匹配個數，若str[i]和str[j]相匹配，則dp[i][j]=dp[i+1][j?1]+2$dp[i][j] = dp[i+1][j-1]+2$，枚舉k為區間i~j的分段點，狀態轉移方程為dp[i][j]=max(dp[i][k]，dp[k+1][j])$dp[i][j] = max(dp[i][k]， dp[k+1][j])$。

程序代碼：

Brackets Sequence

POJ 1141 Let us define a regular brackets sequence in the following way:

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters ‘(‘, ‘)’, ‘[‘, and ‘]’ is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 … an is called a subsequence of the string b1 b2 … bm, if there exist such indices 1 = i1 < i2 < … < in = m, that aj = bij for all 1 = j = n.

題意： 增加最少的括號使給定的括號序列匹配。

思路： 定義dp[i][j]$dp[i][j]$為上題含義。 dp2[i][j]$dp2[i][j]$表示i~j序列應從哪一個位置切斷，若i位置和j位置上括號匹配，dp2[i][j]$dp2[i][j]$ = -1 枚舉k位置，每次更新dp值時將dp2[i][j]=k$dp2[i][j] = k$

采用遞歸打印 若i=j$i=j$，打印”()”或”[]” 若i<j$i<j$，根據dp2[i][j]$dp2[i][j]$的正負來遞歸 程序代碼：

You Are the One

hdu 4283 The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the show itself. The show is hold in the Small hall, so it attract a lot of boys and girls. Now there are n boys enrolling in. At the beginning, the n boys stand in a row and go to the stage one by one. However, the director suddenly knows that very boy has a value of diaosi D, if the boy is k-th one go to the stage, the unhappiness of him will be (k-1)*D, because he has to wait for (k-1) people. Luckily, there is a dark room in the Small hall, so the director can put the boy into the dark room temporarily and let the boys behind his go to stage before him. For the dark room is very narrow, the boy who first get into dark room has to leave last. The director wants to change the order of boys by the dark room, so the summary of unhappiness will be least. Can you help him?

題意： 有一個隊列，每個人有一個憤怒值D，如果他是第K個上場，不開心指數就為(K-1)*D。但是邊上有一個小黑屋（其實就是個堆棧），可以一定程度上調整上場程序，求憤怒值和最小值。

思路： 定義dp[i][j]$dp[i][j]$為i~j序列憤怒和最小值 若第i個人第k個上場，k?[1,j?i+1]$k/epsilon[1, j-i+1]$，狀態轉移方程為 dp[i][j]=min(array[i]?(k?1)+dp[i+1][i+k?1]+dp[i+k][j]+(sum[j]?sum[i+k?1])?k)$dp[i][j] = min(array[i] * (k-1) + dp[i+1][i+k-1] + dp[i+k][j] + (sum[j] - sum[i+k-1]) * k)$， 其中array[i]?(k?1)$array[i] * (k-1)$表示第i個人憤怒值， dp[i+1][i+k-1]表示前i-1個人憤怒值和，dp[i+k][j] + (sum[j] - sum[i+k-1]) * k表示第i個人之后人憤怒值和。

程序代碼：

String painter

hdu2476 There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of Operations?

題意： 求從A字串到B字串需要的最小步驟，每一步驟可以將一段字串變為同一字母字串

思路： 分兩步。

定義dp[i][j] 為空字串到B字串需要的最小步驟， 設初值dp[i][j]=dp[i+1][j]+1$dp[i][j] = dp[i+1][j] + 1$, 當前目標為i，枚舉k?[i+1,j]$k/epsilon[i+1, j]$，若strB[i]=strB[k]$strB[i] = strB[k]$，表示可將i~k變為一種字母，之后處理dp[i+1][k]$dp[i+1][k]$ 狀態轉移方程為：dp[i][j]=min(dp[i+1][k]+dp[k+1][j])$dp[i][j] = min(dp[i+1][k] + dp[k+1][j])$

定義dp2[i] 為A字串到B字串0~i序列的最小步驟， 設初值dp2[i]=dp[0][i]$dp2[i] = dp[0][i]$, 若strA[i]=strB[j]，則dp2[i]=dp2[i?1]$strA[i] = strB[j]， 則dp2[i] = dp2[i-1]$， 狀態轉移方程： dp2[i]=min(dp2[j]+dp[j+1][i])$dp2[i] = min(dp2[j] + dp[j+1][i])$

程序代碼：