2 条题解

  • 0
    @ 2025-10-8 16:56:57

    20分（没快读 + O(n³)）：

    #include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			scanf("%d",&a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
        for(int j=i;j<=m;j++)
		{
            for(int k=i-1;k<=j-1;k++)
            {
                if(f[i-1][k]+a[i][j]>f[i][j])
                {
                    f[i][j]=f[i-1][k]+a[i][j];
                    pre[i][j]=k;
                }
            }
        }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;
    printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}

    40分（快读+O(n³)）：

    #include<bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;x=x*f;
}
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];
int main()
{
    int n,m;qr(n);qr(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			qr(a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
        for(int j=i;j<=m;j++)
		{
            for(int k=i-1;k<=j-1;k++)
            {
                if(f[i-1][k]+a[i][j]>f[i][j])
                {
                    f[i][j]=f[i-1][k]+a[i][j];
                    pre[i][j]=k;
                }
            }
        }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;
    printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}

    80分（没快读+O(n²)）：

    #include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			scanf("%d",&a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
    {
        int t=-0x3f3f3f3f,p=0;
        for(int j=i;j<=m;j++)
		{
            if(t<f[i-1][j-1])t=f[i-1][j-1],p=j-1;
            f[i][j]=t+a[i][j];
            pre[i][j]=p;
        }
    }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}

    100分（快读+O(n²)）：

    #include<bits/stdc++.h>using namespace std;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;x=x*f;
}

const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];

int main()
{
    int n,m;qr(n);qr(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			qr(a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
    {
        int t=-0x3f3f3f3f,p=0;
        for(int j=i;j<=m;j++)
		{
            if(t<f[i-1][j-1])t=f[i-1][j-1],p=j-1;f[i][j]=t+a[i][j];pre[i][j]=p;
        }
    }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}
    • 0
      @ 2025-10-8 16:56:37

      20分（没快读 + O(n^3) ）：

      #include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			scanf("%d",&a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
        for(int j=i;j<=m;j++)
		{
            for(int k=i-1;k<=j-1;k++)
            {
                if(f[i-1][k]+a[i][j]>f[i][j])
                {
                    f[i][j]=f[i-1][k]+a[i][j];
                    pre[i][j]=k;
                }
            }
        }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;
    printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}

      40分（快读+O(n^3)）： 
      #include<bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];
int main()
{
    int n,m;qr(n);qr(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			qr(a[i][j]);

      memset(f,0xC0,sizeof(f));
 
for(int j=1;j&lt;=m;j++)f[1][j]=a[1][j];

for(int i=2;i&lt;=n;i++)
    for(int j=i;j&lt;=m;j++)
	{
        for(int k=i-1;k&lt;=j-1;k++)
        {
            if(f[i-1][k]+a[i][j]&gt;f[i][j])
            {
                f[i][j]=f[i-1][k]+a[i][j];
                pre[i][j]=k;
            }
        }
    }

int x=n,y=n;for(int j=n+1;j&lt;=m;j++)if(f[n][y]&lt;f[n][j])y=j;
printf("%d\n",f[x][y]);
int len=0;
for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
for(int i=len;i&gt;=1;i--) printf("%d ",res[i]);
return 0;

      

      }

      80分（没快读+O(n^2)）：</p> 
      #include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
			scanf("%d",&a[i][j]);
			
	memset(f,0xC0,sizeof(f));
	 
    for(int j=1;j<=m;j++)f[1][j]=a[1][j];

    for(int i=2;i<=n;i++)
    {
        int t=-0x3f3f3f3f,p=0;
        for(int j=i;j<=m;j++)
		{
            if(t<f[i-1][j-1])t=f[i-1][j-1],p=j-1;
            f[i][j]=t+a[i][j];
            pre[i][j]=p;
        }
    }
    
    int x=n,y=n;for(int j=n+1;j<=m;j++)if(f[n][y]<f[n][j])y=j;
    printf("%d\n",f[x][y]);
    int len=0;
    for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
    for(int i=len;i>=1;i--) printf("%d ",res[i]);
    return 0;
}

      100分（ 快读+O(n^2) ） : 
      #include<bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}

      const int N=5010;
int a[N][N],f[N][N],pre[N][N],res[N];
      

      int main()
{
int n,m;qr(n);qr(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
qr(a[i][j]);
      

      memset(f,0xC0,sizeof(f));
 
for(int j=1;j&lt;=m;j++)f[1][j]=a[1][j];

for(int i=2;i&lt;=n;i++)
{
    int t=-0x3f3f3f3f,p=0;
    for(int j=i;j&lt;=m;j++)
	{
        if(t&lt;f[i-1][j-1])t=f[i-1][j-1],p=j-1;
        f[i][j]=t+a[i][j];
        pre[i][j]=p;
    }
}

int x=n,y=n;for(int j=n+1;j&lt;=m;j++)if(f[n][y]&lt;f[n][j])y=j;
printf("%d\n",f[x][y]);
int len=0;
for(int i=x,j=y;i;j=pre[i][j],i--) res[++len]=j;
for(int i=len;i&gt;=1;i--) printf("%d ",res[i]);
return 0;

      

      }
      </p>
      • 1

      *【动态规划：区间二维一边推】矩阵选数[P1854]花店橱窗布置（数据加强）

      信息

      ID
      1399
      时间
      2000ms
      内存
      512MiB
      难度
      9
      标签
      递交数
      346
      已通过
      26
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 10ms
      4. Powered by Hydro v5.0.1 Community