1.背包问题（模板）
经典的背包九讲：
01背包，完全背包，多重背包。
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int MAX=100000; 7 int dp[MAX]; 8 int c[MAX],w[MAX]; 9 int v;10 11 void ZeroOnePack(int cost,int wei) //01背包12 {13 int i;14 for(i = v;i>=cost;i--)15 {16 dp[i] = max(dp[i],dp[i-cost]+wei);17 }18 }19 20 void CompletePack(int cost,int wei) //完全 背包21 {22 int i;23 for(i = cost;i<=v;i++)24 {25 dp[i] = max(dp[i],dp[i-cost]+wei);26 }27 }28 29 void MultiplePack(int cost,int wei,int cnt) //多重 背包30 {31 if(v<=cnt*cost)//如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包32 {33 CompletePack(cost,wei);34 return ;35 }36 else//否则就将多重背包转化为01背包37 {38 int k = 1;39 while(k<=cnt)40 {41 ZeroOnePack(k*cost,k*wei);42 cnt = cnt-k;43 k = 2*k;44 }45 ZeroOnePack(cnt*cost,cnt*wei);46 }47 }48 49 int main()50 {51 int n;52 while(~scanf("%d%d",&n,&v),n+v)53 {54 int i;55 for(i = 0;i
二维背包
hdu 2159
思路：这题是一道典型的二维完全背包题，很明显，背包内所要储存的是经验，所以背包的容量便以忍耐度与杀怪数作为标准，每次得到背包价值的最大数与升级所需的经验作比较， 能够升级就退出。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 const int maxn = 200; 9 int n , m , k , s;10 int a[maxn] , b[maxn] , dp[maxn][maxn];11 12 int main()13 {14 while(scanf("%d%d%d%d", & n, &m, &k, &s) !=EOF)15 {16 memset(dp , 0 , sizeof(dp));17 for(int i = 1;i <= k;i ++)18 {19 scanf("%d%d", &a[i] , &b[i]);20 }21 int i , j , z;22 for(i = 1;i <= m;i ++) // 主要限制要放在种数前23 {24 for(j = 1;j <= k;j ++)25 {26 for(z = 1;z <= s;z ++)27 {28 int ans = 1;29 while(ans * b[j] <= i && ans <= z) 30 { 31 dp[i][z] = max(dp[i][z],dp[i - ans * b[j]][z-ans] + ans*a[j]); 32 ans ++; 33 } 34 } 35 }36 if(dp[i][s] >= n)37 break;38 }39 if(i > m)40 printf("-1\n");41 else42 printf("%d\n",m - i);43 }44 return 0;45 }
2、LIS和LCS
最长递增子序列，朴素的是O(n^2)算法，二分下可以写成O(nlgn)：维护一个当先最优的递增序列——找到恰好大于它更新。
最长公共子序列，通常O(n^2)；