题解

175 条题解

  • 4
    @ 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
    @ 2018-01-03 14:46:30
    #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
    @ 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
    @ 2017-10-21 13:32:28

    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
    @ 2017-09-29 16:45:06

    双线程dp
    150ms

    dp[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
    @ 2019-03-10 16:29:16

    暴力

    #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
    @ 2015-10-28 19:39:47

    //定义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
    @ 2017-07-20 20:41:27

    时间空间都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
    @ 2017-07-14 09:34:18

    三维过

    #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
    @ 2017-05-10 15:02:18

    #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
    @ 2017-02-11 15:21:29

    #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
    @ 2016-10-28 23:51:00

    #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
    @ 2016-09-03 22:55:12

    我就想问这题跟方格取数有一点点不一样吗?
    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
    @ 2016-08-09 08:58:28

    #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
    @ 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
    @ 2016-07-15 15:38:58

    #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;
    }
    //偷懒大法好

    • @ 2018-02-04 20:24:21

      这个偷懒6啊,学到了
      Huaji

  • 0
    @ 2016-05-14 15:52:08

    #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
    @ 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
    @ 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;
    }

信息

ID
1493
难度
5
分类
动态规划 点击显示
标签
递交数
6684
已通过
2495
通过率
37%
被复制
6
上传者