不看题解写不出来系列……

第一篇状压DP。

题目描述

给出如下定义:

  1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

例如,下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的子矩阵如右图所示。

9 3 3 3 9

9 4 8 7 4

1 7 4 6 6

6 8 5 6 9

7 4 5 6 1

的其中一个2*3的子矩阵是

4 7 4

8 6 9

  1. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
  2. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个n行m列的正整数矩阵,请你从这个矩阵中选出一个r行c列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

PJ比TG难系列。

dfs一下选哪些行,处理一下前缀和,然后按照列DP一下就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int sumx[20]={0},sumy[20][20]={0},sizex,sizey,r,c,mapx[20][20]={0};
int f[20][20]={0},ansall=1e7;  //f[i][j]表示在前i个中选取j个
bool vis[20]={false};

inline void initsum()
{
    memset(sumx,0,sizeof(sumx));
    memset(sumy,0,sizeof(sumy));
    register int prex=0,prex2=0;
    while (1)
    {
        prex++;
        if (vis[prex]) break;
    }

    for (register int i=prex+1;i<=sizex;i++) if (vis[i])
    {
        for (register int j=1;j<=sizey;j++) sumx[j]+=abs(mapx[i][j]-mapx[prex][j]);
    	prex=i;
    }

    for (int i=1;i<=sizey;i++)
        for (int j=i-1;j>=1;j--)
        	for (int k=1;k<=sizex;k++) if (vis[k])
            	sumy[i][j]+=abs(mapx[k][i]-mapx[k][j]);
    return;
}

inline int dp()
{
    register int ans=1e7;
    memset(f,0x7f,sizeof(f));
    
    for (int i=0;i<=sizey;i++) 
	{
		f[i][0]=0;
		f[i][1]=sumx[i];
	}

    for (register int i=1;i<=sizey;i++)
    	for (register int j=2;j<=c && j<=i;j++)
    		for (register int k=j-1;k<i;k++)
            	f[i][j]=min(f[i][j],f[k][j-1]+sumx[i]+sumy[i][k]);

    for (int i=c;i<=sizey;i++) ans=min(ans,f[i][c]);
    return ans;
}

void dfs_x(int nowr,int step)
{
    if (step==r)
    {
        initsum();
        ansall=min(ansall,dp());
        return;
    }
    for (int i=nowr+1;i<=sizex;i++)
    {
        if (!vis[i]) 
		{
			vis[i]=true;
			dfs_x(i,step+1);
    		vis[i]=false;
		}
    }
    return;
}

int main()
{
    scanf("%d%d%d%d",&sizex,&sizey,&r,&c);
    for (int i=1;i<=sizex;i++)
        for (int j=1;j<=sizey;j++) 
			scanf("%d",&mapx[i][j]);

    dfs_x(0,0);
    printf("%d\n",ansall);
    return 0;
}

 

分类: 状压DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.