3、小球放盒子-动态规划
    有 N 个相同的球，M 个不同的盒子，每个盒子最多放K 个球，请计算将这N个球全部放入盒子中的方案数模 1000007 后的结果
    输入：三个正整数，依次为 N，M，K
    输出：输出方案数模 1000007 后的结果
    样例输入 4 2 3
    样例输出 3
    提示 总共有 3 种方案，依次为 { 3 ， 1 }，{ 2 ， 2 }，{ 1 ，3 }。
    对于100%的数据，N，M ≤ 5000 

    1. #include<bits/stdc++.h>
    2. typedef long long ll;
    3. using namespace std;
    4. const int MAXN=5e3+10;
    5. const int MOD=1000007;
    6. int N,M,K;
    7. ll ways[MAXN][MAXN];
    8. int main() {
    9.     cin>>N>>M>>K;
    10.     for(int i=1; i<=M; i++) ways[i][0]=1;
    11.     for(int m=1; m<=M; m++) {
    12.         int sum=m;
    13.         for(int n=1; n<=N; n++) {
    14.             ways[m][n]=sum;
    15.             sum=(sum+ways[m-1][n+1])%MOD;
    16.             if(n-K>=0) sum=(sum-ways[m-1][n-K]+MOD)%MOD;
    17.         }
    18.     }
    19.     cout<<ways[M][N]<<endl;
    20.     return 0;
    21. }

    4、最大子矩阵
    已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是 1 1)子矩阵。 比如，如下 4 4 的矩阵
    0 -2 -7 0
    9 2 -6 2
    -4 1 -4 1
    -1 8 0 -2
    的最大子矩阵是
    9 2
    -4 1
    -1 8
    这个子矩阵的大小是 15。
    输入：输入是一个 N N 的矩阵。输入的第一行给出 N (0 N = 100)。再后面的若干行中，依次（首先从左到右给出第一行的 N 个整数，再从左到右给出第二行的N 个整数……）给出矩阵中的 N2 个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。
    输出：输出最大子矩阵的大小。
    样例输入 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
    样例输出 15 

    1. #include<iostream>
    2. #include<cmath>
    3. using namespace std;
    4. int a[1001][1001],b[1001][1001];
    5. int main() {
    6.     int n;
    7.     int x,y;
    8.     int num,sum;
    9.     cin>>n;
    10.     for(int i=1; i<=n*n; i++) {
    11.         cin>>num;
    12.         x=(i-1)/n+1;
    13.         y=i%n;
    14.         if(y==0)
    15.             y=n;
    16.         a[x][y]=num;
    17.     }
    18.     for(int i=1; i<=n; i++)
    19.         for(int j=1; j<=n; j++)
    20.             b[i][j]=b[i-1][j]+a[i][j];
    21.     int max=b[1][1];
    22.     for(int i=1; i<=n; i++)
    23.         for(int j=i; j<=n; j++) {
    24.             sum=0;
    25.             for(int k=1; k<=n; k++) {
    26.                 if(sum>0)
    27.                     sum+=b[j][k]-b[i-1][k];
    28.                 else
    29.                     sum=b[j][k]-b[i-1][k];
    30.                 if(sum>max)
    31.                     max=sum;
    32.             }
    33.         }
    34.     cout<<max<<endl;
    35.     return 0;
    36. }

    6、酒鬼
    Santo 刚刚与房东打赌赢得了一间在 New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo 高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。”现在可怜的 Santo 站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。
    输入：第一行一个整数 N,有 N 个酒瓶。N<=700 接下有N 行，第I+1 行的数字代表酒瓶 I 中酒的体积。
    输出：一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。
    样例输入 6 6 10 13 9 8 1
    样例输出: 33 

    1. #include<iostream>
    2. #include<algorithm>
    3. using namespace std;
    4. const int N = 710;
    5. int n , ans, dp[N][2], b[N];
    6. int main() {
    7.     scanf("%d", &n);
    8.     for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    9.     dp[1][0] = 0;
    10.     dp[1][1] = b[1];
    11.     for(int i = 1; i <= n; i++) {
    12.         dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
    13.         dp[i][1] = dp[i - 1][0] + b[i];
    14.         dp[i][2] = dp[i - 1][1] + b[i];
    15.     }
    16.     ans = max(dp[n][0], max(dp[n][1], dp[n][2]));
    17.     printf("%d", ans);
    18.     return 0;
    19. }