4 条题解
-
3Xian (XianYu) LV 5 @ 2021-10-10 11:28:53
#include <iostream> using namespace std; const int N = 60; int a[N][N]; int dp[N][N][N][N]; int main(){ int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int x = 1; x <= n; x ++){ for(int y = 1; y <= m; y++){ int *t; t = &dp[i][j][x][y]; *t = max(*t, dp[i-1][j][x][y-1]); *t = max(*t, dp[i-1][j][x-1][y]); *t = max(*t, dp[i][j-1][x-1][y]); *t = max(*t, dp[i][j-1][x][y-1]); *t += a[i][j] + a[x][y]; if(i == x && j == y) *t -= a[x][y]; } } } } cout << dp[n][m][n][m]; }
-
02024-12-17 13:30:10@
#include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define int long long #define void inline void queue<int> Q; stack<int> S; vector<int> V; #ifndef SOMETHING_H #define SOMETHING_H #endif #define int long long inline int read(){ char c = getchar(); int s = 0; while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9'){ s = s * 10 + c - '0'; c = getchar(); } return s; } int n, m, ans[52][52][52][52], a[52][52]; inline int f(int x1, int y1, int x2, int y2){ if(x1 == n && x2 == n && y1 == m && y2 == m) return 0; if(ans[x1][y1][x2][y2] != -1) return ans[x1][y1][x2][y2]; int kkk = 0; if(x1 < n && x2 < n) if(a[x1 + 1][y1] != -1 && a[x2 + 1][y2] != -1) kkk = max(kkk, f(x1 + 1, y1, x2 + 1, y2) + a[x1 + 1][y1] + a[x2 + 1][y2] - a[x1 + 1][y1] * (x1 == x2 && y1 == y2)); if(y1 < m && y2 < m) if(a[x1][y1 + 1] != -1 && a[x2][y2 + 1] != -1) kkk = max(kkk, f(x1, y1 + 1, x2, y2 + 1) + a[x1][y1 + 1] + a[x2][y2 + 1] - a[x1][y1 + 1] * (x1 == x2 && y1 == y2)); if(x1 < n && y2 < m) if(a[x1 + 1][y1] != -1 && a[x2][y2 + 1] != -1) kkk = max(kkk, f(x1 + 1, y1, x2, y2 + 1) + a[x1 + 1][y1] + a[x2][y2 + 1] - a[x1 + 1][y1] * (x1 + 1 == x2 && y1 == y2 + 1)); if(y1 < m && x2 < n) if(a[x1][y1 + 1] != -1 && a[x2 + 1][y2] != -1) kkk = max(kkk, f(x1, y1 + 1, x2 + 1, y2) + a[x1][y1 + 1] + a[x2 + 1][y2] - a[x1][y1 + 1] * (x1 == x2 + 1 && y1 + 1 == y2)); ans[x1][y1][x2][y2] = kkk; return kkk; } void Main(){ n = read(); m = read(); memset(ans, -1, sizeof(ans)); for(int i = 1; i <= n; i++) for(int o = 1; o <= m; o++) a[i][o] = read(); cout << f(1, 1, 1, 1); return; } signed main(int argc, char **argv){ Main(); return 0; }
-
02023-12-10 20:47:50@
#include<bits/stdc++.h> using namespace std; const int N=55; int m,n,a[N][N],dp[N][N][N]; int main(){ cin>>m>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=m;k++){ int l=i+j-k; if(l>=1&&l<=n) { int temp=max(max(dp[i-1][j][k-1],dp[i-1][j][k]),max(dp[i][j-1][k-1],dp[i][j-1][k])); dp[i][j][k]=temp+a[i][j]; if(i!=k) dp[i][j][k]+=a[k][l]; } } cout<<dp[m][n][m]<<endl; return 0; }
-
-42021-8-8 1:33:00@
C++ :
#include<bits/stdc++.h> using namespace std; int a[51][51],n,m; unsigned int s[51][51][51][51]; int main(int argc,char*argv[]){ memset(a,0,sizeof(a)); memset(s,0,sizeof(s)); scanf("%d%d",&m,&n); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); } int a1,a2; for(int j=1;j<=n;j++){ for(int k=1;k<=m;k++){ for(int l=1;l<=n;l++){ a1=max(s[i][j-1][k][l-1],s[i-1][j][k][l-1]); a2=max(s[i-1][j][k-1][l],s[i][j-1][k-1][l]); s[i][j][k][l]=max(a1,a2)+a[i][j]+a[k][l]; if(i==k&&j==l)s[i][j][k][l]-=a[i][j]; } } } } printf("%d",s[m][n][m][n]); return 0; }
- 1
信息
- ID
- 186
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 42
- 已通过
- 32
- 上传者