1. 题目列表

• POJ3267（字符串匹配dp）
• POJ1836（LIS最长上升子序列的变形：最长先上升后下降子序列长度）
• POJ1260（连续的区间dp：掌握思想）
• POJ2533

2. DP问题思路

DP问题一般求最小代价或最大代价，dp数组往往定义为前i个最小代价或最大代价的和。找到dp[i]与dp[i-1]或dp[1~i-1]之间的状态转移方程，求解问题。
状态转移方程往往具有以下的形式：

3. POJ1836——Alignment

3.1 题目描述

Description

In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight line in front of the captain. The captain is not satisfied with the way his soldiers are aligned; it is true that the soldiers are aligned in order by their code number: 1 , 2 , 3 , . . . , n , but they are not aligned by their height. The captain asks some soldiers to get out of the line, as the soldiers that remain in the line, without changing their places, but getting closer, to form a new line, where each soldier can see by looking lengthwise the line at least one of the line's extremity (left or right). A soldier see an extremity if there isn't any soldiers with a higher or equal height than his height between him and that extremity.

Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.
Input

On the first line of the input is written the number of the soldiers n. On the second line is written a series of n floating numbers with at most 5 digits precision and separated by a space character. The k-th number from this line represents the height of the soldier who has the code k (1 <= k <= n).

There are some restrictions:
• 2 <= n <= 1000
• the height are floating numbers from the interval [0.5, 2.5]
Output

The only line of output will contain the number of the soldiers who have to get out of the line.

Sample Input

8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
Sample Output

4

3.2 解决思路

题意：对于任意一个士兵满足：其与端点之一间的士兵身高不超过他，
即求先严格递增后严格递减的最长序列长度。

思路：从左到右、右到左分别求LIS， 
res = n - max(dp1[i] + dp2[j])(j = i + 1,...,n)
即1~i的最大递增长度加上i+1~n的最大递减长度 

3.3 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
/*
    题意：对于任意一个士兵满足：其与端点之一间的士兵身高不超过他，
    即求先严格递增后严格递减的最长序列长度。
    
    思路：从左到右、右到左分别求LIS， 
    res = n - max(dp1[i] + dp[j])(j = i + 1,...,n)
    即1~i的最大递增长度加上i+1~n的最大递减长度 
*/
const int maxn = 1010;
int dp1[maxn], dp2[maxn]; // dp1 1~i最长LIS，dp2 i~n最长LIS 
double h[maxn];

int main(){
    int n;
    scanf("%d", &n);
    fill(dp1 + 1, dp1 + 1 + n, 1);
    fill(dp2 + 1, dp2 + 1 + n, 1);
    for (int i = 1; i <= n; i++){
        scanf("%lf", &h[i]);
        for (int j = 1; j < i; j++)
            if (h[i] > h[j])
                dp1[i] = max(dp1[i], dp1[j] + 1);
    }
    for (int i = n; i >= 1; i--){
        for (int j = n; j > i; j--){
            if (h[i] > h[j])
                dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
    int MAX = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            MAX = max(MAX, dp1[i] + dp2[j]);
    printf("%d\n", n - MAX);
    return 0;
}

4. POJ1260——Pearls

4.1 题目描述

Description

In Pearlania everybody is fond of pearls. One company, called The Royal Pearl, produces a lot of jewelry with pearls in it. The Royal Pearl has its name because it delivers to the royal family of Pearlania. But it also produces bracelets and necklaces for ordinary people. Of course the quality of the pearls for these people is much lower then the quality of pearls for the royal family.In Pearlania pearls are separated into 100 different quality classes. A quality class is identified by the price for one single pearl in that quality class. This price is unique for that quality class and the price is always higher then the price for a pearl in a lower quality class.
Every month the stock manager of The Royal Pearl prepares a list with the number of pearls needed in each quality class. The pearls are bought on the local pearl market. Each quality class has its own price per pearl, but for every complete deal in a certain quality class one has to pay an extra amount of money equal to ten pearls in that class. This is to prevent tourists from buying just one pearl.
Also The Royal Pearl is suffering from the slow-down of the global economy. Therefore the company needs to be more efficient. The CFO (chief financial officer) has discovered that he can sometimes save money by buying pearls in a higher quality class than is actually needed.No customer will blame The Royal Pearl for putting better pearls in the bracelets, as long as the
prices remain the same.
For example 5 pearls are needed in the 10 Euro category and 100 pearls are needed in the 20 Euro category. That will normally cost: (5+10)10+(100+10)20 = 2350 Euro.Buying all 105 pearls in the 20 Euro category only costs: (5+100+10)*20 = 2300 Euro.
The problem is that it requires a lot of computing work before the CFO knows how many pearls can best be bought in a higher quality class. You are asked to help The Royal Pearl with a computer program.

Given a list with the number of pearls and the price per pearl in different quality classes, give the lowest possible price needed to buy everything on the list. Pearls can be bought in the requested,or in a higher quality class, but not in a lower one.
Input

The first line of the input contains the number of test cases. Each test case starts with a line containing the number of categories c (1<=c<=100). Then, c lines follow, each with two numbers ai and pi. The first of these numbers is the number of pearls ai needed in a class (1 <= ai <= 1000).
The second number is the price per pearl pi in that class (1 <= pi <= 1000). The qualities of the classes (and so the prices) are given in ascending order. All numbers in the input are integers.
Output

For each test case a single line containing a single number: the lowest possible price needed to buy everything on the list.

Sample Input

2
2
100 1
100 2
3
1 10
1 11
100 12
Sample Output

330
1344

4.2 解决思路

题意：给定n商品的价格和需求量（价格递增），求在满足需求量情况下，
最少需要花多少钱，并限制买第i个商品时，必须要多买10个，且高价格的商品
可以替换低价格的商品。

思路：由于高价商品可以替换低价商品，所以总购买价格可能会更低。
定义：
    dp[i]表示分析到第i个商品时，当前的最小花费总和； 
    sum[i]表示分析第i个商品时，所需购买的总数 
此外，替代是连续的，不可能出现跳跃替代，即3替代1，5替代2，此时3替代2比5替代2更优。 

根据以上思路，状态转移方程：
dp[i] = min(dp[i-1] + (a[i] + 10) * p[i], dp[j]+(sum[i] - sum[j] + 10) * price[i]), j = 0,1,...,i-1
意义：根据替代的连续性，分析到第i类产品时，判断第j~i类的商品是否可使用第i类商品替代使得总花费最小
边界条件：dp[0] = 0 

5. POJ3267——The Cow Lexicon

5.1 题目描述

Description

Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

Input

Line 1: Two space-separated integers, respectively: W and L
Line 2: L characters (followed by a newline, of course): the received message
Lines 3..W+2: The cows' dictionary, one word per line
Output

Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer
Sample Output

2

5.2 解决思路

题意：给定一个大小为W的字典，输入一个word，问至少去掉几个字母能够
使得该word是该字典中的一系列单词。

思路：穷举需要2^{300}次，显然超时。

定义：
    dp[i]为1~i个字符能所需要删除的最小字符数。
    例1：browndcodw 
    (下标从0)dp:[0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 2]
    例2：broswincdow
    dp:[0, 1, 2, 3, 4, 5, 6, 3, 4, 5, 6, 4] 
    
状态转移方程：
  dp[i]= dp[j - 1] + 多余的字符数, if str[1~i]母串匹配字典中的词k，j为匹配的边界
  dp[i] = dp[i - 1] + 1, else 
边界条件：dp[0] = 0 
注意：在匹配的时候要倒序更新。

例子：如遇到最后一个字符'w'时，遍历整个字典。
初始化 dp[index('w')] = dp[index('w') - 1] + 1 =5 
1. 首先碰到第一个匹配的词brown，则
dp[index('w')] = max(5,dp[index('b')-1]+'browndcodw'匹配'brown'多余的字符个数)
=max(5,0 + 5) = 5

2. 其次碰到第二个匹配的词cow，则
dp[index('w')] = max(5,dp[index('c') - 1]) + 'codw'匹配'cow'多余的字符个数)
=max(5,1 + 1) = 2

5.3 代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int dp[310];
char dict[610][28], word[310]; 
int main(){ 
    int w, l;
    scanf("%d%d", &w, &l);
    scanf("%s", word + 1);
    for (int i = 0; i < w; i++)
        scanf("%s", dict[i]);
    dp[0] = 0;
    for (int i = 1; i <= l; i++){
        // 未优化
        dp[i] = dp[i - 1] + 1; 
        // 倒序判断1~i的母串是否能匹配字典中的串
        for (int k = 0; k < w; k++){
            int u = i;
            int v = strlen(dict[k]) - 1;
            for (; u >= 1; u--){
                if (word[u] == dict[k][v])
                    v--;
                if (v < 0) break;
            }
            if (v < 0){
                if (dp[i] > dp[u - 1] + i - u + 1 - strlen(dict[k]))
                    dp[i] = dp[u - 1] + i - u + 1 - strlen(dict[k]);
            }
        } 
    }
    printf("%d\n", dp[l]);
    return 0;
}