#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来写，也不容易