先对从左到右对每一行进行dp,再类似地从上到下dp,两次dp!
#include <vector> #include <list> #include <map> #include <set> #include <queue> #include <string> #include <deque> #include <stack> #include <algorithm> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <limits.h> #include <time.h> #include <string.h> using namespace std; int lowbit(int t){return t&(-t);} int countbit(int t){return (t==0)?0:(1+countbit(t&(t-1)));} int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);} #define LL long long #define PI acos(-1.0) #define N 200001 #define Max INT_MAX #define Min INT_MIN #define eps 1e-8 #define FRE freopen("a.txt","r",stdin) int dp1[N],b[N],dp2[N]; int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ int i,j,k; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ int a; scanf("%d",&a); dp1[0]=0; if(j==1)dp1[j]=a; else{ dp1[j]=max(dp1[j-1], dp1[j-2]+a); } } b[i]=dp1[m]; } dp2[1]=b[1]; dp2[0]=0; for(i=2;i<=n;i++) dp2[i]=max(dp2[i-1],dp2[i-2]+b[i]); printf("%d\n",dp2[n]); } return 0; }