关键词：
Description
Summer is coming! It‘s time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix a with n lines and m columns. Let number a[i][j] represents the calories burned by performing workout at the cell of gym in thei-th line and the j-th column.
Iahub starts with workout located at line 1 and column 1. He needs to finish with workout a[n][m]. After finishing workout a[i][j], he can go to workout a[i + 1][j] or a[i][j + 1]. Similarly, Iahubina starts with workout a[n][1] and she needs to finish with workouta[1][m]. After finishing workout from cell a[i][j], she goes to either a[i][j + 1] or a[i - 1][j].
There is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout.
If a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.
Input
The first line of the input contains two integers n and m (3 ≤ n, m ≤ 1000). Each of the next n lines contains m integers: j-th number from i-th line denotes element a[i][j] (0 ≤ a[i][j] ≤ 105).
Output
The output contains a single number — the maximum total gain possible.
Sample Input
3 3 100 100 100 100 1 100 100 100 100
800
代码：注意一点，交点不能在边界，如果在边界不满足两人只相遇一次的条件。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int mp[1005][1005]; int dp1[1005][1005],dp2[1005][1005],dp3[1005][1005],dp4[1005][1005]; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&mp[i][j]); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(dp3,0,sizeof(dp3)); memset(dp4,0,sizeof(dp4)); for(int i=1; i<=n; i++)//右下 for(int j=1; j<=m; j++) dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])+mp[i][j]; for(int i=n; i>=1; i--)//右上 for(int j=1; j<=m; j++) dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+mp[i][j]; for(int i=1; i<=n; i++)//左下 for(int j=m; j>=1; j--) dp3[i][j]=max(dp3[i-1][j],dp3[i][j+1])+mp[i][j]; for(int i=n; i>=1; i--)//左上 for(int j=m; j>=1; j--) dp4[i][j]=max(dp4[i+1][j],dp4[i][j+1])+mp[i][j]; int ans=0; for(int i=2; i<n; i++) for(int j=2; j<m; j++) { ans=max(ans,dp1[i-1][j]+dp2[i][j-1]+dp3[i][j+1]+dp4[i+1][j]); ans=max(ans,dp1[i][j-1]+dp2[i+1][j]+dp3[i-1][j]+dp4[i][j+1]); } printf("%d ",ans); } return 0; }
cf429epointsandsegments欧拉回路
【CF429E】PointsandSegments题意：给你数轴上的n条线段$[l_i,r_i]$，你要给每条线段确定一个权值+1/-1，使得：对于数轴上的任一个点，所有包含它的线段的权值和只能是+1,-1或0。$n\le10^5$题解：首先，我们用扫描线，整个数轴被分成若... 查看详情
cf935dfafaandancientalphabet概率dp(递推)(代码片段)
D.FafaandAncientAlphabet(简洁题意请往下翻)timelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAncientEgyptiansareknowntohaveusedalargesetofsymbols towriteont 查看详情
[递推]aw3777.砖块(思维+递推+cf1271b)(代码片段)
....题目解析1.题目来源链接：3777.砖块2.题目解析经典的递推问题，也有类似问题，翻硬币问题。这种开关问题也可以拓展到二维平面上，枚举第一行的所有状态，递推即可，时间复杂度是O(2n)O(2^n)O(2n)。当数... 查看详情
cf429bb.workingout（四角dp）(代码片段)
题意：两个人一个从左上角一个从左下角分别开始走分别走向右下角和右上角，（矩阵每个格子有数）问到达终点后可以得到的最大数是多少，并且条件是他们两个相遇的时候那个点的数不能算思路：首先这道题如果暴力搜索一... 查看详情
cf166e在四面体上寻找路线数递推，取模(代码片段)
来源：codeforces E.Tetrahedron Youaregivenatetrahedron.Let‘smarkitsverticeswithletters A, B, C and D co 查看详情
cf429epointsandsegments(代码片段)
Link把红蓝分别看成(+1,-1)，然后给序列差个分，我们要做的就是给一个无向图中的边定向使得存在一条欧拉回路。因为度数可能是奇数所以补一些(0)边就行了。#include<bits/stdc++.h>#defineN1000007usingnamespacestd;namespaceIOcharibuf[(1<<... 查看详情
cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)
LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai!=ai+2,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情
cf1140epalindrome-lessarrays(巧妙的递推)(代码片段)
LINK题意一个数组有些位置是???,你可以使用[1,k][1,k][1,k]填充满足最后对于i∈[1,n−2]i\\in[1,n-2]i∈[1,n−2]有ai!=ai+2a_i!=a_i+2ai!=ai+2,求方案数我们分成奇数索引构成的数组和偶数索引构成的数组分别考虑现在设奇... 查看详情
[9.26]cf每日一题系列——771b递推问题
Description： 给定你命名的规律，1-10个字符，开头必须大写，最多有50个名字，然后告诉你有n个人，判断区间长度为k，那么你将得到n-k+1个答案（YESorNO）表示1-k,2-k+1,n-K+1-—n这些人里面是否没有重名，YES没有，NO有，让你推出... 查看详情
[递推]aw1208.翻硬币(递推+蓝桥杯第四届省赛cb)(代码片段)
...目来源链接：1208.翻硬币相同题，不同场景：[递推]aw3777.砖块(思维+递推+CF1271B)2.题目解析经典递推题目，思路和[递推]aw3777.砖块(思维+递推+CF1271B)一样，数据保证一定有解，无解情况需要判断操... 查看详情
cf1051dbicolorings递推
考试T2，随便推一推就好了~code:#include<bits/stdc++.h>#defineN1015#definemod998244353#definelllonglong#definesetIO(s)freopen(s".in","r",stdin),freopen(s".out","w",stdout)usingnamespacestd;llf[N][N<<1][2][2];intmain() //setIO("army"); inti,j,n=2,m,k; scanf("%d%d",&m,&k);... 查看详情
cf697e&&cf696cplease
...简，然后对1e9+7取模。题解：首先我们可以轻易得到一个递推式：$d[i]=frac{{1-d[i-1]}}{2}$但递推式是不行的，我们要得到一个封闭形式。运用数列技巧，我们可以进行如下变换：$d[i]-frac{1}{ 查看详情
cf821e.okabeandelpsykongroo矩阵快速幂
...求走y坐标所夹范围，那么就简单多了，很容易看出是个递推形DP，然而数据量有点大，k为10的18次，一般转移显然不可行。由于是个递推，而且y坐标最大也只有15 查看详情
bdp个人版产品体验报告：在线数据分析使用心得
BDP个人版作为国内海致公司旗下的数据可视化分析产品，因其简单的拖拽操作、直观的可视化效果等，逐渐成为运营、产品等互联网人的必备数据工具。BDP目前处于产品成长期，发展势头良好，作为路转粉用户，本文我将从... 查看详情
[递推]aw95.费解的开关(二维递推+开关问题+二进制枚举)(代码片段)
...目来源2.题目解析1.题目来源链接：95.费解的开关一维递推：[递推]aw3777.砖块(思维+递推+CF1271B)2.题目解析这个是十字形改变灯的状态的，并且只有5*5的棋盘大小，所以总的状态数量是25∗52^5*525∗5暴力枚举肯... 查看详情
phpcp-证书与-bdp-fields.php(代码片段)
cf15etriangles(代码片段)
...只走上面的小三角形然后组合方案数\(2f^2+8f+10\)然后求f，递推一下就好啦（其实是太麻烦了）时间和空间复杂度都是\(O(n)\)代码#include<cstdio>#include<cstring>#include<algorithm>#defineintlonglongusingnamespacestd;con 查看详情
2021银川bdp(代码片段)
题意n个数分为要求分为1~n个子数组，每个子数组贡献为最大值减最小值n=1e4思路考虑dp,dp[i][j][k]代表前i个数分为j个组，当前到了0/1/2/3状态，0代表最大数和最小数都没选，1代表选了最大数，2代表选了最小... 查看详情