题解：P2258 [NOIP2014 普及组] 子矩阵

· · 题解

题目地址

题目使用 n^3 dp做法最佳

因为还要枚举从哪里转移过来

而对于 \max / \min 的这种转移

一般还可以用单调队列优化dp使复杂度降一维

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
const int N=20;
int min=2147482647;
int map[N][N];
int qu[N];
int n,m,r,c;
int xx[N],yy[N][N];
int f[N][N];
void dp()
{
    memset(xx,0,sizeof(xx));
    memset(yy,0,sizeof(yy));
    memset(f,127,sizeof(f));
    for(int i=1;i<=m;i++)
    for(int j=2;j<=r;j++)
    xx[i]+=abs(map[qu[j]][i]-map[qu[j-1]][i]);

    for(int i=1;i<=m;i++)
    for(int j=i+1;j<=m;j++)
    for(int k=1;k<=r;k++)
    yy[i][j]+=abs( map[qu[k]][i]-map[qu[k]][j]);

    for(int i=1;i<=m;i++)   f[i][0]=0,f[i][1]=xx[i];

    for(int i=1;i<=m;i++)
    for(int j=2;j<=c;j++)
    {
        for(int k=1;k<i;k++)
        f[i][j]=std::min(f[i][j],f[k][j-1]+yy[k][i]+xx[i]);
    }
    for(int i=1;i<=m;i++)
    min=std::min(min,f[i][c]);
}
void dfs(int i,int step)
{
    if(step==r+1)   
    {
        dp();
        return;
    }
    if(n-i<r-step)  return;
    for( ;i<=n;i++) 
    qu[step]=i,dfs(i+1,step+1);
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&r,&c);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&map[i][j]);
    dfs(1,1);
    printf("%d\n",min);
    return 0;
}