【题目大意】
在n*m的矩阵中，每个格子都有一个权值a，求一个包含k个格子的凸连通块，使这个连通块中的格子的权值和最大。
【思路分析】
任何一个凸连通块都可以分成连续的若干行，每行的左端点列号先递减后递增，右端点列号先递增后递减。我们可以依次考虑从n*m矩阵中的每一行中选择哪些格子来构成所求的凸连通块，那么我们需要关注的信息有：
1.当前已经处理完的行数i
2.已经选出的格子数j
3.当前行已选格子的左端位置l——为了确定下一行左端点的范围，以满足单调性
4.当前行已选格子的右端位置r——为了确定下一行右端点的范围，以满足单调性
5.当前左侧轮廓的单调性类型x——递增(0)还是递减(1)
6.当前右侧轮廓的单调性类型y——递增(0)还是递减(1)
于是我们设f[i][j][l][k][x][y]表示前i行选了j个格子，其中第i行选择了第l到r个格子，左边界单调性为x，右边界单调性为y时，构成的凸连通块的最大权值之和。
接着可以列出状态转移方程：
1.左减右增
$$f[i][j][l][r][1][0]=\sum_{p=l}^{r}a[i][p]$$
$$if(j=r-l+1>0)\to f[i][j][l][r][1][0]+=f[i-1][0][0][0][1][0]$$
$$if(j>r-l+1>0)\to f[i][j][l][r][1][0]+=max\{f[i-1][j-(r-l+1)][p][q][1][0]\}(l\le p\le q\le r)$$
2.左减右减
$$f[i][j][l][r][1][1]=\sum_{p=l}^{r}a[i][p]+max\{max\{f[i-1][j-(r-l+1)][p][q][1][y]\}(0\le y\le 1)\}(l\le p\le r\le q)$$
3.左增右增
$$f[i][j][l][r][0][0]=\sum_{p=l}^{r}a[i][p]+max\{max\{f[i-1][j-(r-l+1)][p][q][x][0]\}(0\le x\le 1)\}(l\le p\le r\le q)$$
4.左增右减
$$f[i][j][l][r][0][1]=\sum_{p=l}^{r}a[i][p]+max\{max\{max\{f[i-1][j-(r-l+1)][p][q][x][y]\}(0\le y\le 1)\}(0\le x\le 1)\}(l\le p\le r\le q)$$
初始值：f[i][0][0][0][1][0]=0
目标：$max\{f[i][k][l][r][x][y]\}$
因为本题还要输出方案，所以我们可以用一个数组在DP过程中记录最优解是由哪一个状态转移过来的，这样就可以在最后递归一下得到方案了。
【代码实现】