175 条题解
-
4
ljt12138 LV 10 @ 2016-07-24 09:29:58
其实需要证明一下，两条路线发生冲突当且仅当某一位置时重合。
分类讨论：设由(1,2)->(m-1, n)的路径为P，(2,1)->(m,n-1)的路径为Q。由题意得，两条路径中每一点能且仅能向右或向下。或者说，任何一个点来自其左或上方。
如果P和Q在某一点A发生冲突，则(1,1)->A的|P|和|Q|一定等于(1,1)->A的曼哈顿距离（小学奥数）。原问题得证 -
2
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> int c[51][51]; int f[120][51][51]; int n, m; int re=0; int _max(int a, int b, int c, int d) { int x=std::max(a, b); int y=std::max(c, d); return std::max(x, y); } void solve() { int s; f[2][1][1]=0; for(int k=3; k<m+n; k++) for(int i=1; i<=n; i++) for(int j=1+i; j<=n; j++) { s=_max(f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]); s=std::max(f[k][i][j], s); if(s==-1) continue; f[k][i][j]=s+c[i][k-i]+c[j][k-j]; } } int main() { memset(f, -1, sizeof f); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &c[i][j]); solve(); printf("%d", f[m+n-1][n-1][n]); return 0; } -
2
2351599120 LV 9 @ 2017-10-28 10:13:58
本题数据较小
四维暴力DP即可#include<bits/stdc++.h> using namespace std; int a[55][55]; int f[55][55][55][55]; int main() { int n,m,maxx=0; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=m;k++) { for(int l=1;l<=n;l++) { maxx=0; if(i!=k&&j!=l||i==k&&k==m&&j==l&&l==n) { maxx=max(f[i-1][j][k-1][l],maxx); maxx=max(f[i][j-1][k][l-1],maxx); maxx=max(f[i-1][j][k][l-1],maxx); maxx=max(f[i][j-1][k-1][l],maxx); f[i][j][k][l]=maxx+a[i][j]+a[k][l]; } } } } } printf("%d",f[m][n][m][n]); return 0; } -
2
var
m,n,i,j,k,l:longint;
f:array[0..51,0..51,0..51,0..51]of longint;
a:array[0..51,0..51]of longint;
function max(a,b,c,d,e:longint):longint;
begin
max:=0;
if a>max then max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
if e>max then max:=e;
end;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
for i:=1 to m do
for j:=1 to n do
for k:=1 to m do
for l:=1 to n do
begin
f[i,j,k,l]:=max(f[i,j-1,k-1,l],f[i,j-1,k,l-1],f[i-1,j,k-1,l],f[i-1,j,k,l-1],f[i,j,k,l])+a[i,j];
if (i<>k)and(j<>l) then f[i,j,k,l]:=f[i,j,k,l]+a[k,l];
end;
writeln(f[m,n,m,n]);
end. -
2
双线程dp
150msdp[i][j][k][l]指由i→j同时由k→l
显然如果重合点不要做由于另一个题解所写：
其实需要证明一下，两条路线发生冲突当且仅当某一位置时重合。
分类讨论：设由(1,2)->(m-1, n)的路径为P，(2,1)->(m,n-1)的路径为Q。由题意得，两条路径中每一点能且仅能向右或向下。或者说，任何一个点来自其左或上方。
如果P和Q在某一点A发生冲突，则(1,1)->A的|P|和|Q|一定等于(1,1)->A的曼哈顿距离（小学奥数）。原问题得证所以可以压成三维（因为是曼哈顿距离）
四维写法
#include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } const int N=55,M=55; int ma[N][M],n,m; int dp[55][55][55][55]; int main() { n=read(); m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ma[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) for(int l=1;l<=m;l++) { int maxn=0; if((i!=k&&j!=l)||(i==k&&k==n)&&(j==l&&l==m)) //事实上只需要i!=k，不需要同时j!=l { maxn=max(dp[i-1][j][k-1][l],maxn); maxn=max(dp[i][j-1][k][l-1],maxn); maxn=max(dp[i-1][j][k][l-1],maxn); maxn=max(dp[i][j-1][k-1][l],maxn); dp[i][j][k][l]=maxn+ma[i][j]+ma[k][l]; } } printf("%d\n",dp[n][m][n][m]); return 0; }三维写法（直接复制的别人的）：
#include <iostream> #include <cstring> #include <cstdio> #define maxn 55 using namespace std; int f[2 * maxn][maxn][maxn]; int a[maxn][maxn]; int n,m; int max_ele(int a,int b,int c,int d){ if (b>a) a = b; if (c>a) a = c; if (d>a) a = d; return a; } int main(){ cin >> n >> m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin >> a[i][j]; for (int k=1;k<=n+m-1;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ if (k-i+1<1 || k-j+1<1) //这里是判断纵坐标的合法性，如果纵坐标不合法那就跳过去 continue; f[k][i][j] = max_ele(f[k-1][i][j],f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j]) + a[i][k-i+1] + a[j][k-j+1]; if (i==j) //判断重合路径 f[k][i][j]-=a[i][k-i+1];} cout << f[n+m-1][n][n] << endl; return 0; } -
1
暴力
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std; const int inf = 0x3f3f3f3f; int m,n,maxn; int d[55][55][55][55],g[55][55]; int main(){ ios::sync_with_stdio(false); cin >> m>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) cin>>g[i][j]; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ for(int x=1;x<=m;x++){ for(int y=1;y<=n;y++){ if(i==x&&j==y&&(i!=m||j!=n)&&(i!=1||j!=1)){ d[i][j][x][y] = -inf; continue; } maxn = 0; maxn = max(d[i-1][j][x-1][y],maxn); maxn = max(d[i-1][j][x][y-1],maxn); maxn = max(d[i][j-1][x-1][y],maxn); maxn = max(d[i][j-1][x][y-1],maxn); d[i][j][x][y] = maxn + g[i][j]+g[x][y]; } } } } cout<<d[m][n][m][n]; return 0; } -
1
//定义f[i][j][k]表示第i步时 下面这条线路在横坐标为j的位置，上边的线路在横坐标为k的位置的最大好心值。要注意k>=j 除了最后一个终点
//f[i][j][k]=max(f[i-1][j-1][k-1],f[i-1][j-1][k],f[i-1][j][k-1],f[i-1][j][k]) +v[j][i-j+1]+v[k][i-k+1]
#include <cstdio>
#include <algorithm>
using namespace std;
long long m,n,v[60][60],f[300][60][60];long long max(long long a,long long b){return a>b?a:b;}
int main(){
freopen("1493.in","r",stdin);freopen("1493.out","w",stdout);
scanf("%lld%lld",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++) scanf("%lld",&v[i][j]);
for(int i=1;i<=m+n-1;i++)
for(int j=0;j<=i&&j<=m;j++)
for(int k=j;k<=i&&k<=m;k++){//注意这里k和j的最大值
if(j!=k||i==m+n-1){
if(j<k-1) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]);
if(j-1<k) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);
if(j-1<k-1) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]);
if(j<k) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
f[i][j][k]=f[i][j][k]+v[j][i-j+1]+v[k][i-k+1];
}
}
printf("%lld",f[m+n-1][m][m]);
return 0;
} -
0
时间空间都n^2
#include<iostream>
#include<cstdio>
using namespace std;
int maxx(int a ,int b,int c,int d)
{
int ans;
ans=max(a,b);
ans=max(ans,c);
ans=max(ans,d);
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("ans1.txt","w",stdout);int a[51][51];
int g[2][51][51];
memset(g,0,sizeof(g));
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int c=0,d=m+n;
for(int k=2;k<=d;k++)
{
c=c^1;
for(int i=1;i<k;i++)
{
if(i>n||k-i>m) continue;
for(int j=1;j<i;j++)
{
if(j>n||k-j>m)continue;g[c^1][i][j]=maxx(g[c][i-1][j],
g[c][i][j-1],
g[c][i][j],
g[c][i-1][j-1])+a[i][k-i]+a[j][k-j];
}
}
}
cout<<g[c][n][n-1]<<endl; -
0
三维过
#include <stdio.h> int x1, x2, y1, y2; int dp[51][51][51]; int map[51][51]; int m, n; int max(int a, int b, int c, int d) { if(a < b)a = b; if(a < c)a = c; if(a < d)a = d; return a; } int main() { scanf("%d%d", &m, &n); for(x1 = 1; x1 <= m; x1++) for(y1 = 1; y1 <= n; y1++) scanf("%d", &map[x1][y1]); for(x1 = 1; x1 <= m; x1++) for(y1 = 1; y1 <= n; y1++) for(x2 = 1; x2 <= m; x2++) { if (x1 + y1 - x2 > 0) y2 = x1 + y1 - x2; else break; dp[x1][y1][x2] = max(dp[x1 - 1][y1][x2 - 1], dp[x1][y1 - 1][x2 - 1], dp[x1 - 1][y1][x2], dp[x1][y1 - 1][x2]) + map[x1][y1] + map[x2][y2]; if (x1 == x2 && y1 == y2) dp[x1][y1][x2] -= map[x1][y1]; } printf("%d", dp[m][n][m]); } -
0
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int maxn = 53;
int juzhen[maxn][maxn];
int dp[2 * maxn][maxn][maxn];int max_(int a,int b,int c,int d){
int maxm = 0;
maxm = max(maxm,a);
maxm = max(maxm,b);
maxm = max(maxm,c);
maxm = max(maxm,d);
return maxm;
}int main(){
int a,b;
cin >> a >> b;
for(int p = 1;p <= a;p++){
for(int q = 1;q <= b;q++) cin >> juzhen[p][q];
}
memset(dp,0,sizeof(dp));
for(int i = 3;i <= a + b;i++){
for(int p = 1;p <= a;p++){
if(i - p > b || i - p < 1)continue;
for(int q = 1;q <= a;q++){
if(i - q > b || i - q < 1)continue;
if(p == q && i < a + b)continue;
dp[i][p][q] = max_(dp[i - 1][p][q],dp[i - 1][p - 1][q - 1],dp[i - 1][p][q - 1],dp[i - 1][p - 1][q]) + juzhen[p][i - p] + juzhen[q][i - q];
}
}
}
cout << dp[a + b][a][a];
} -
0
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
short seat[51][51];
short f[51][51][51][51];
bool used[51][51][51][51];
int main(){// freopen("1002.in","r",stdin);
// freopen("1002.out","w",stdout);
int m,n;
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&seat[i][j]);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
for(int l=1;l<=n;l++){
if(used[i][j][k][l]==0){
if(used[i][j][k][l]==0)
{
int a=max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]);
int b=max(f[i-1][j][k][l-1],f[i][j-1][k-1][l]);
f[i][j][k][l]=max(a,b)+seat[i][j];
if(i!=k&&j!=l) f[i][j][k][l]+=seat[k][l];
used[i][j][k][l]=1;
}
}
}
}
}
}
printf("%d",f[m][n][m][n]);
// printf("\n%.6lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
} -
0
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int f[60][60][60][60];
int a[60][60];
int m,n;
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
f[1][1][1][1]=0;
for(int i=m;i>=1;i--)
for(int j=n;j>=1;j--)
for(int k=m;k>=1;k--)
for(int l=n;l>=n;i--)
{
if((i!=k||j!=l)||(i==m&&k==m&&j==n&&l==n)||(i==1&&k==1&&l==1&&j==1))
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i][j-1][k-1][l]),max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]))+a[i][j];
cout<<f[m][n][m][n];
return 0;
}
} -
0
我就想问这题跟方格取数有一点点不一样吗？
var
m,n,i,j,k,l:longint;
f:array[0..51,0..51,0..51,0..51]of longint;
a:array[0..51,0..51]of longint;
function max(a,b,c,d,e:longint):longint;
begin
max:=0;
if a>max then max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
if e>max then max:=e;
end;begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
for i:=1 to m do
for j:=1 to n do
for k:=1 to m do
for l:=1 to n do
begin
f[i,j,k,l]:=max(f[i,j-1,k-1,l],f[i,j-1,k,l-1],f[i-1,j,k-1,l],f[i-1,j,k,l-1],f[i,j,k,l])+a[i,j];
if (i<>k)and(j<>l) then f[i,j,k,l]:=f[i,j,k,l]+a[k,l];
end;
writeln(f[m,n,m,n]);
end. -
0
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int n,m;
int t[55][55],f[55][55][55][55];
int main (){
scanf ("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf ("%d",&t[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=n;k++)
for (int l=1;l<=m;l++){
int maxn=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]));
if (i==k&&j==l)
f[i][j][k][l]=t[k][l]+maxn;
else
f[i][j][k][l]=t[i][j]+t[k][l]+maxn;
}
printf("%d",f[n][m][n][m]);
return 0;
} -
0
Angelwings LV 8 @ 2016-08-09 08:57:44
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<string> #include<cstring> using namespace std; int n,m; int t[55][55],f[55][55][55][55]; int main (){ scanf ("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf ("%d",&t[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) for (int l=1;l<=m;l++){ int maxn=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])); if (i==k&&j==l) f[i][j][k][l]=t[k][l]+maxn; else f[i][j][k][l]=t[i][j]+t[k][l]+maxn; } printf("%d",f[n][m][n][m]); return 0; } -
0
#include<iostream>
#define fr(x,a,y) for(int x=1;x<=a;x+=y)
#define f(a,b,c,d) f[a][b][c][d]
#define a(x,y) a[x][y]
using namespace std;
int n,m,a[51][51]={0},sumn=0;
int f[51][51][51][51];
int main()
{
int x,y;
cin>>m>>n;
fr(i,m,1)
fr(j,n,1)
{
cin>>a[i][j];
}
fr(i,m,1)fr(j,n,1)fr(k,m,1)fr(l,n,1)
{
f(i,j,k,l)=max(max(f(i-1,j,k-1,l),f(i-1,j,k,l-1)),max(f(i,j-1,k-1,l),f(i,j-1,k,l-1)))+a(i,j)+a(k,l);
if(i==k&&j==l)
f[i][j][k][l]=f[i][j][k][l]-a[i][j];
}
cout<<f(m,n,m,n);
return 0;
}
//偷懒大法好-
HigHwind @ 2018-02-04 20:24:21
这个偷懒6啊，学到了
-
-
0
#include <iostream>
using namespace std;
int h[51][51],f[100][51][51];
int main()
{
int m,n;
cin>>m>>n;
int i,j,k;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>h[i][j];
for(i=1;i<=m+n-1;i++)
for(j=0;j<=i&&j<=m;j++)
for(k=j;k<=i&&k<=m;k++) //k在j之下
{
if(j!=k || i==m+n-1)
{
if(k>j-1)
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);//j从上，k从左
if(k-1>j)
f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]);//j从左，k从上
if(k-1>j-1)
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]);//j从上，k从上
if(k>j)
f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);//j从左，k从左f[i][j][k]=f[i][j][k]+h[j][i-j+1]+h[k][i-k+1];
}
}
cout<<f[m+n-1][m][m];
return 0;
} -
0
1277937546 LV 8 @ 2015-10-13 21:12:35
var
f:array[0..100,0..50,0..50] of longint;
a:array[1..50,1..50] of longint;
i,j,k,m,n:longint;
function max(aa,bb,cc,dd:longint):longint;
begin
max:=aa;
if bb>max then max:=bb;
if cc>max then max:=cc;
if dd>max then max:=dd;
end;
begin
read(m,n);
for i:=1 to m do
for j:=1 to n do read(a[i,j]);
fillchar(f,sizeof(f),0);
for i:=1 to (m+n) do
for j:=1 to m do
for k:=1 to m do
if (i>j)and(i>k) then begin
f[i,j,k]:=max(f[i-1,j,k],f[i-1,j-1,k],f[i-1,j,k-1],f[i-1,j-1,k-1])+a[j,i-j];
if (j<>k)or((i-j)<>(i-k)) then f[i,j,k]:=f[i,j,k]+a[k,i-k];
end;
writeln(f[m+n,m,m]);
end. -
0
-
0
2868647513 LV 8 @ 2015-09-06 21:06:09
#include<cstdio>
#include<cstring>
#define fr(i,n) for(int i=1;i<=n;i++)
int n,x,y,z,m;
int a[51][51];
int sum[51][51][51][51];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d%d",&n,&m);
fr(i,n)
fr(j,m)
scanf("%d",&a[i][j]);
fr(i,n)
fr(j,m)
fr(h,n)
fr(k,m)
{
sum[i][j][h][k]=max(max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]),
max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]))+a[i][j];
if (i!=h&&j!=k)
sum[i][j][h][k]+=a[h][k];
}
printf("%d\n",sum[n][m][n][m]);
return 0;
}
ljt12138
LV 10
@ 2016-07-24 09:29:58
