[NOIP 2014復習]第二章：動態規劃——NOIP歷屆真題回顧
背包型動態規劃
1、Wikioi 1047 郵票面值設計
題目描述 Description
給定一個信封，最多只允許粘貼N張郵票，計算在給定K（N+K≤40）種郵票的情況下（假定所有的郵票數量都足夠），如何設計郵票的面值，能得到最大值MAX，使在1～MAX之間的每一個郵資值都能得到。
例如，N=3，K=2，如果面值分別為1分、4分，則在1分～6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）；如果面值分別為1分、3分，則在1分～7分之間的每一個郵資值都能得到。可以驗證當N=3，K=2時，7分就是可以得到的連續的郵資最大值，所以MAX=7，面值分別為1分、3分。
輸入描述 Input Description
N和K
輸出描述 Output Description
每種郵票的面值，連續最大能到的面值數。數據保證答案唯一。
樣例輸入 Sample Input
3 2
樣例輸出 Sample Output
1 3
MAX=7
很好的一道題！實際上這個題是個DFS搜索題，通過DFS搜索下一個可以出現的郵票面值，但是得到郵票面值後需要求出能湊出的最大郵資，如果光用枚舉，雖然數據范圍不大，但是算上去也是個很大的常數了，加上DFS搜索次數太多，這樣做會超時，比較好的辦法就是用完全背包f[v]表示湊出郵資v最少要多少張郵票，每次得到一個郵票面值，就記錄下它，用“我為人人”型動規更新f數組，然後從小到大搜索一遍下一種郵票面值，直到所有郵票面值都枚舉完，更新最大郵資
另外需要注意的是搜索下一種郵票面值時，也不能亂枚舉，這樣會讓搜索樹中每個節點的兒子太多，搜索樹就會太大，一樣會超時，那麼枚舉就得有上下界。
下界的求法是，枚舉的下一種郵票面值要保證比上一種大，這樣郵票面值序列就會是單調遞增的，很明顯，下界是之前求出的郵票面值中的最後一種面值x+1，簡單證明：
如果下一種郵票面值應該小於之前的郵票，由於郵票面值序列是單調遞增的，那麼它不應該在這個時候搜索，而應該早就被搜過了，不會輪到現在這麼晚搜。
而枚舉面值的上界是當前所有郵票能湊出的連續最大郵資sum，簡單證明：
之前出現的郵資連續區間是[1,sum],而下一張郵票面值是sum+1,則加上下一張郵票面值後，連續區間為[1,sum]∩[sum+2,sum*2+1],而郵資sum+1取不到，實際上連續最大郵資還是sum沒變，說明下一張郵票面值取得太大了
若下一張郵票面值是sum,則加上下一張郵票面值後，連續區間為[1,2*sum]，答案變大了，郵票面值取得剛好。
這樣一來此題思路就清晰了，下面是代碼
#include
#include
#include
#define MAXV 1000
#define MAXN 40
#define INF 1000000
int f[MAXV],stamp[MAXN],nowSol[MAXN],maxValue; //f[v]=湊出面額v至少要多少張郵票，stamp是保存面值的數組,nowSol是當前DFS搜出的郵票面值,max=當前最大總面值
int n,k;
void dfs(int cnt,int sum) //已經有了cnt種郵票（當前正在嘗試第cnt+1種郵票），而且
{
int copy[MAXV]; //拷貝數組f用
if(cnt==k) //所有郵票的面值都枚舉完了
{
if(sum>maxValue) //如果當前的最大總面值超過之前的答案，那麼這是新的最優解
{
maxValue=sum;
for(int i=1;i<=cnt;i++)
stamp[i]=nowSol[i];
}
return;
}
for(int i=0;i
棋盤型動態規劃
1、Wikioi 1043 方格取數
題目描述 Description
設有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。如下圖所示（見樣例）：
某人從圖的左上角的A 點出發，可以向下行走，也可以向右走，直到到達右下角的B點。在走過的路上，他可以取走方格中的數（取走後的方格中將變為數字0）。
此人從A點到B 點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
輸入描述 Input Description
輸入的第一行為一個整數N（表示N*N的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的0表示輸入結束。
輸出描述 Output Description
只需輸出一個整數，表示2條路徑上取得的最大的和。
樣例輸入 Sample Input
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
樣例輸出 Sample Output
67
和之前的傳紙條很類似，思路基本相同，照搬即可，這裡不細說，但有個細節需要注意：這裡兩條路徑是可以重合的，由於題目中有這個要求，所以動規時不能避開兩個相同的點，如圖
若兩條路徑有交叉(DP中兩個點相同)，那麼就把重復算入的當前格子分數扣掉就行了。
#include
#include
#include
#define MAXN 50
long long int f[MAXN][MAXN][MAXN][MAXN];
long long int n,map[MAXN][MAXN];
long long int max(long long int a,long long int b)
{
if(a>b) return a;
return b;
}
int main()
{
scanf("%lld",&n);
int x,y,num;
while(1)
{
scanf("%d%d%d",&x,&y,&num);
if(!x&&!y&&!num) break;
map[x][y]=num;
}
for(int i=1;i<=n;i++) //第一條路徑過點(i,j)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
for(int h=1;h<=n;h++)
{
f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k-1][h]);
f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h-1]);
f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k-1][h]);
f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k][h-1]);
f[i][j][k][h]+=map[i][j]+map[k][h];
if(i==k&&j==h) f[i][j][k][h]-=map[i][j];
}
printf("%lld\n",map[n][n]+max(f[n-1][n][n][n-1],f[n][n-1][n-1][n]));
return 0;
}
區間型動態規劃
1、Wikioi 1090 加分二叉樹
題目描述 Description
設一個n個節點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第j個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
若某個子樹為主，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空
子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
（1）tree的最高加分
（2）tree的前序遍歷
現在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。
輸入描述 Input Description
第1行：一個整數n（n<=30），為節點個數。
第2行：n個用空格隔開的整數，為每個節點的分數（分數<=100）
輸出描述 Output Description
第1行：一個整數，為最高加分（結果不會超過4,000,000,000）。
第2行：n個用空格隔開的整數，為該樹的前序遍歷。
樣例輸入 Sample Input
5
5 7 1 2 10
樣例輸出 Sample Output
145
3 1 2 4 5
數據范圍及提示 Data Size & Hint
n（n<=30)
分數<=100
乍一看這個題是數據結構題，但是因為一個中序遍歷對應多個二叉樹，這個題沒辦法建樹，好像做不出來，但是細想NOIP怎麼可能會考這麼裸的二叉樹呢？所以這個題是個區間型動規題，為了寫起來方便，最好是用記憶化DFS來寫，也不容易錯。
可以用一個二元組（或者說區間左右端點）[L,R]表示當前遞歸層次的狀態，dfs(L,R)=求區間[L,R]對應二叉樹子樹能獲得的最大分數，為了能在線段區間中模擬樹結構的遞歸深搜過程，可以進行下圖的操作
動規的思路也很清晰，套用區間型動規的通用方程就行，f[L,R]=max{f[L,mid-1]*f[mid+1,R]+value[mid]},這裡mid就是要取的子樹根結點
#include
#include
#include
#define MAXN 100
int f[MAXN][MAXN]; //f[i][j]=中序遍歷序列區間[1,j]獲得分數的最大值
int visit[MAXN][MAXN];
int root[MAXN][MAXN];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int dp(int L,int R) //
{
if(L==R) return f[L][R];
if(L>R) return 1;
if(visit[L][R]) return f[L][R];
visit[L][R]=1;
int maxAns=-1;
for(int mid=L;mid<=R;mid++)
if(maxAns<(dp(L,mid-1)*dp(mid+1,R)+f[mid][mid]))
{
root[L][R]=mid;
int Ltree=dp(L,mid-1);
int Rtree=dp(mid+1,R);
maxAns=(Ltree*Rtree+f[mid][mid]);
}
return f[L][R]=maxAns;
}
void firstPrint(int L,int R)
{
if(L>R) return;
printf("%d ",root[L][R]);
firstPrint(L,root[L][R]-1);
firstPrint(root[L][R]+1,R);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i][i]);
root[i][i]=i;
}
printf("%d\n",dp(1,n));
firstPrint(1,n);
printf("\n");
system("pause");
return 0;
}
序列型動態規劃
1、Wikioi 1058 合唱隊形
題目描述 Description
N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1<...Ti+1>…>TK(1<=i<=K)。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
輸入描述 Input Description
輸入文件chorus.in的第一行是一個整數N(2<=N<=100)，表示同學的總數。第一行有n個整數，用空格分隔，第i個整數Ti(130<=Ti<=230)是第i位同學的身高(厘米)。
輸出描述 Output Description
輸出文件chorus.out包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。
樣例輸入 Sample Input
8
186 186 150 200 160 130 197 220
樣例輸出 Sample Output
4
數據范圍及提示 Data Size & Hint
對於50％的數據，保證有n<=20；
對於全部的數據，保證有n<=100。
此題可以用最長上升子序列和最長下降子序列做，不過有些細節需要處理，如圖
#include
#include
#include
#define MAXN 300
int high[MAXN]; //high[i]=第i個同學的身高
int up[MAXN],dn[MAXN];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&high[i]);
up[i]=dn[i]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(high[j]=1;i--)
for(int j=n;j>=i;j--)
if(high[j]
