A．Grandpa's Rubik Cube
PKU 1290
http://poj.org/problem?id=1290
題意：給定一個3X3的六面魔方（每個面有3X3個塊），求經(jīng)過某些旋轉(zhuǎn)之后能否使得所有面的顏色都相同，旋轉(zhuǎn)包括對某個面進行順時針和逆時針旋轉(zhuǎn)（共12種情況）。
圖A-1
如圖1，輸入數(shù)據(jù)為左圖的形式，右圖給對應(yīng)的面編號，箭頭方向為順時針旋轉(zhuǎn)方向。
+A表示對A這個面進行一次順時針旋轉(zhuǎn)，-B表示對B這個面進行一次逆時針旋轉(zhuǎn)。問經(jīng)過一定的+A/-B操作之后能否使得所有面的3X3個字母都相同。
題解：模擬題
做法很多，這里介紹一種比較容易理解的狀態(tài)記錄方式，考慮某次旋轉(zhuǎn)，一定是旋轉(zhuǎn)某個面，然后對鄰接的四個面的某條邊進行順次平移。如圖A-2, 2號面的旋轉(zhuǎn)帶動的是1、5、3、6四個面。
圖A-2
我用一個數(shù)組rotate_n來記錄某個面旋轉(zhuǎn)的時候帶動的面的編號集合（編號為0的數(shù)據(jù)為占位符），那么有：
int rotate_n [7][4] = {
{0, 0, 0, 0}, {4, 5, 2, 6}, {1, 5, 3, 6}, {2, 5, 4, 6}, {3, 5, 1, 6}, {1, 4, 3, 2}, {1, 2, 3, 4}
};
光記錄帶動的面是哪些還不夠，還需要知道帶動面的對應(yīng)邊，對于一個魔方的一個面，我們編號如下：
（0,0）（0,1）（0,2）
（1,0）（1,1）（1,2）
（2,0）（2,1）（2,2）
分別用1到4來代表一個面的四條邊（注意，有方向）：
1 (0,2) - (0,0)
2 (2,2) - (0,2)
3 (2,0) - (2,2)
4 (0,0) - (2,0)
那么同樣用rotate_p來記錄某個面旋轉(zhuǎn)的時候帶動的面對應(yīng)的邊，則有：
int rotate_p[7][4] = {
{0, 0, 0, 0}, {2, 4, 4, 4}, {2, 3, 4, 1}, {2, 2, 4, 2}, {2, 1, 4, 3}, {1, 1, 1, 1}, {3, 3, 3, 3},
};
這樣一來，我們只需要考慮一個面的旋轉(zhuǎn)，然后套用對應(yīng)的數(shù)據(jù)即可，還有一個比較巧妙的是，逆時針旋轉(zhuǎn)不需要特殊處理，直接將順時針旋轉(zhuǎn)執(zhí)行三次即可。
B．This Sentence is False
PKU 1291 http://poj.org/problem?id=1291
題意：給定一些句子形如“Sentence X is true/false”的句子，X表示第幾個句子，問所有的情況是否合法，如果合法，輸出最大的可能為真的句子。
題解：2-sat。
每個句子抽象成兩個結(jié)點，為真的時候為X，為假的時候為X '。
a) 對于第X個句子，如果是 Sentence Y is true；
則這個句子為真的時候， X ->Y連邊；
當這個句子為假的時候，X ' -> Y '連邊；
b) 對于第X個句子，如果是 Sentence Y is false；
則這個句子為真的時候， X ->Y '連邊；
當這個句子為假的時候，X ' -> Y連邊；
然后求一次強連通，如果最后有某個點X和X ' 在同一個連通圖中，說明邏輯錯誤，說明必然存在不合法的情況，否則對于每個連通分量，求出為真的點的個數(shù)和為假的點的個數(shù)，然后將他們之中的大者累加，最后答案除2就是最大的可能為真的句子（除2的原因是因為真假是對稱的）。
C．Will Indiana Jones Get There?
PKU 1292 http://poj.org/problem?id=1292
題意：營救公主，營救路線要么繞著墻走，要么走兩面墻的最短距離（這種情況下需要在兩面墻之間搭一塊木板，并且可以反復(fù)使用）。問營救過程中木板的最短長度。
圖C-1
題解：線段距離 + 二分答案
因為木板可以反復(fù)使用，所以我們可以假設(shè)如果木板越長，能夠營救公主的概率就越大，反之則越小，所以問題就是求滿足兩點可達的最小木板長度，可以二分枚舉這個長度T，如果兩面墻的最短距離大于這個T，表明兩面墻不可達，將墻抽象成點，兩面墻之間的最短距離可以通過線段和線段的最短距離預(yù)處理出來，然后每次二分答案后通過一次搜索就可以找出起點和終點是否可達，復(fù)雜度為O（n^2）即計算兩線段距離時候的復(fù)雜度。
D. Duty Free Shop
PKU 1293 http://poj.org/problem?id=1293
題意：給定M(M <= 1000)個白巧克力和L(L<= 1000)個黑巧克力，然后給定N(N <= M + L)個容量為Ci的盒子，問能否找到一種方案，使得某些盒子放滿白巧克力，剩下的盒子放滿黑巧克力。
題解：背包問題。
由于需要將每個盒子都放滿，于是可以利用一維背包的求法將Ci的所有小于等于M的可行組合求出來，找到最大的M ' <= M，并且M ' 能夠通過某種方式被組合出來，那么所有盒子的容量Sum 減去 M ' 的差小于等于L的話，必定能將剩下的盒子填滿黑巧克力，否則無解。
這題需要記錄前驅(qū)，并且注意M = 0 以及 L = 0 的情況（主要是在輸入的時候判斷退出條件，M+L==0退出而并非 (M&&L) == 0）。
E．Not Too Convex Hull
PKU 1294 http://poj.org/problem?id=1294
題意：給定N(N<=101)個點（沒有三點共線的情況），要求用B(B<=50)根皮條將這N個點圈成B個部分，每個部分為一個凸多邊形，并且所有凸多邊形公用一個點（這個點會給出），求眾多方案中滿足所有多邊形面積和最小的方案。圖E-1表示用兩根皮條圈住19個點的情況（原點共用了兩次）。
圖E-1
題解：環(huán)形動態(tài)規(guī)劃。
首先將所有點按照給定的原點進行極坐標排序，那么第1個點到第N個點必定是按照極坐標嚴格逆時針排布的（因為沒有三點共線），用DP[i][b]表示第i個點到第N個點經(jīng)過b次分割后分割完的凸多邊形的面積總和最小值，那么：
DP[i][b] =min{ area[i][k] +DP[k+1][b-1] (i < k < N) }; 特殊的，DP[0][0] = 0;
area[i][j] 表示極坐標在第i個點和第j個點之間的所有點(包含這兩個點)加上原點組成的凸包的面積，可以通過初始化預(yù)處理出來；
由于點是極坐標排列的，也就是第一個點不一定是凸包邊上的點（有可能是第N-1個點到第2個點組成的凸包達到整體最優(yōu)），所以需要做N次DP，可以將所有點復(fù)制一份，枚舉起點i ( 1 <= i <= N)，終點即i+N, 然后分別做一次DP取最小值。
時間復(fù)雜度O(N^2 * B)。
F．I hate SPAM, but some people love it
PKU 1295 http://poj.org/problem?id=1295
題意：N(N<=20)個人互發(fā)郵件，某個人收到郵件后一定會回復(fù)給他所有的好友，回復(fù)的數(shù)量決定他的稱號，按順序給定首先發(fā)起郵件的人，要求按順序輸出所有人得到的稱號。
題解：深搜枚舉。
數(shù)據(jù)量很小，對于給定的初始者作為起點進行遍歷，每個人只訪問一次，訪問到的時候根據(jù)他的朋友數(shù)量計算他的稱號即可。
G．Noise Effect
PKU 1296 http://poj.org/problem?id=1296
題意：給定兩個正方形矩陣，求他們的最大相似度，相似度的定義為矩陣元素對應(yīng)位差值小于等于100的個數(shù)占所有矩陣元素的百分比（可以進行旋轉(zhuǎn)和翻轉(zhuǎn)）。
題解：模擬題。
每個矩陣可以進行四次旋轉(zhuǎn)，每次旋轉(zhuǎn)可以有水平翻轉(zhuǎn)、豎直翻轉(zhuǎn)、水平豎直翻轉(zhuǎn)、保持原樣四種狀態(tài)，一共十六種情況（實際小于16種，因為有些狀態(tài)經(jīng)過翻轉(zhuǎn)和旋轉(zhuǎn)之后是一樣的），對每種情況模擬計算相似度取最大值即可。
H．Supermarket
PKU 1297 http://poj.org/problem?id=1297
題意：約翰需要買M(M<=100)件物品，超級市場上的物品都排成一排，一共N(N<=100000)件物品，他從左向右開始選物品，但是為了不麻煩，不想走回頭路，而且第i個物品買的條件是，前i－1個物品必須已經(jīng)買了，但是每個物品在超級市場中的價格不一樣，即使同一個物品也有不同的價格，為了花費最少，他想要一個方案使得：
1) 按順序購買M個物品；
2) 總價值最少，并輸出這個最小值，如果方案不存在，輸出Impossible。
題解：動態(tài)規(guī)劃。
DP[i][j]表示第i個購買列表中的物品和第j個市場中的物品匹配時的最小消費（1<=i<=M,1<=j<=N）;
Min[i][j]表示min{ DP [i][x] x<=j };
a)當?shù)?/span>i個物品和第j個市場物品編號相同時，DP[i][j] = Min[i-1][j-1] +cost[j];
b)否則DP[i][j] = inf; 計算DP數(shù)組同時更新Min數(shù)組，由于每次的狀態(tài)最多和上一行有關(guān)，所以在進行狀態(tài)轉(zhuǎn)移的時候可以采用滾動數(shù)組。時間復(fù)雜度O(NM)。