P2258 [NOIP2014 普及组] 子矩阵

题意

子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。
相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。

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

$1 ≤ n ≤ 16$ ， $1 ≤ m ≤ 16$ ，矩阵中的每个元素 $1 ≤ a_{ij} ≤ 1,000$ ， $1 ≤ r ≤ n$ ， $1 ≤ c ≤ m$ 。

点击查看题解

题解

看到这个数据范围，首先想到可以状压 DP。然而，此题可以利用 dfs 生成组合，提供 DP 方式。

原题要求选出一个 $r$ 行 $c$ 列的子矩阵。我们可以枚举每行选出 $c$ 个元素的位置，使问题转化为从矩阵中选出 $r$ 行的子矩阵。这样的 DP 就很好实现了。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=20,inf=2147483647999999,M=65536+10;
	ll n,m,r,c,a[N][N],t[N],w[M][N],cnt=0,ans=inf;
	ll f[N][N];//在前 u 行选 v 行的最小值，且包含第 u 行 
	ll ws[N][N],hs[N];//行的得分，列的得分 
	void dfs(ll step,ll pre)
	{
		if(step>c)
		{
			cnt++;
			for(ll i=1;i<=c;i++)
				w[cnt][i]=t[i];
			return;
		}
		for(ll i=pre;i<=m;i++)
			t[step]=i,dfs(step+1,i+1);
	}
	void init(ll p)
	{
		for(ll i=1;i<=n;i++)
		{
			ll tmp=0;
			for(ll j=1;j<=c-1;j++)
				tmp+=abs(a[i][w[p][j]]-a[i][w[p][j+1]]);
			hs[i]=tmp;
		}
		for(ll i=1;i<=n;i++)
		{
			for(ll j=i+1;j<=n;j++)
			{
				ll tmp=0;
				for(ll k=1;k<=c;k++)
					tmp+=abs(a[i][w[p][k]]-a[j][w[p][k]]);
				ws[i][j]=tmp;
			}
		}
	}
	void dp()
	{
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=min(i,r);j++)
			{
				if(j==1) f[i][j]=hs[i];
				else{
					f[i][j]=inf;
					for(ll k=j-1;k<=i-1;k++)
						f[i][j]=min(f[i][j],f[k][j-1]+hs[i]+ws[k][i]);
				}
				if(j==r) ans=min(ans,f[i][j]);
			}
		}
	}
	void yzmain()
	{
		scanf("%lld%lld%lld%lld",&n,&m,&r,&c);
		memset(a,0,sizeof(a));
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		dfs(1,1);//枚举方案
		for(ll i=1;i<=cnt;i++)//方案数
			init(i),dp();
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0; 
}

P1006 [NOIP2008 提高组] 传纸条

题意

班上同学安排坐成一个 $m$ 行 $n$ 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端。他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 $(1,1)$ ，小轩坐在矩阵的右下角，坐标 $(m,n)$ 。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

全班每个同学愿意帮忙的好感度有高有低。试找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。 $1 \le m,n \le 50$ 。

点击查看题解

题解

乍看无从下手，但看到 $m$ 和 $n$ 的范围这么小，我们大胆想：可不可以进行四维 DP，分别记录两条路径？答案是可以的。

由于来或去的路径是等价的，所以假设两条路径都是从 $(1,1)$ 走。设 $f(i,j,k,l)$ 表示第一条路径走到 $(i,j)$ ，第二条路径走到 $(k,l)$ 时的最优答案。易得状态转移方程（见代码）。

双倍经验：[NOIP2000 提高组] 方格取数。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=60;
	ll n,m,a[N][N],ans=0;
	ll f[N][N],g[N][N][N][N];
	void dp()
	{
		for(ll i=1;i<=m;i++)
			for(ll j=1;j<=n;j++)
				for(ll k=1;k<=i;k++)
					for(ll l=j;l<=n;l++)
					{
						ll ans=a[i][j]+a[k][l];
						if(i==k&&j==l) ans-=a[i][j];
						g[i][j][k][l]=max(g[i-1][j][k-1][l],
									  max(g[i-1][j][k][l-1],
									  max(g[i][j-1][k-1][l],
									      g[i][j-1][k][l-1])))+ans;
					}
	}
	void yzmain()
	{
		scanf("%lld%lld",&m,&n);
		for(ll i=1;i<=m;i++)
			for(ll j=1;j<=n;j++)
				scanf("%lld",&a[i][j]);
		memset(f,0,sizeof(f));
		dp();ans+=g[m][n][m][n];
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}

P1240 诸侯安置

题意

给定一个 $2 \times n+1$ 行的菱形图，在上面放诸侯，使得同一行和同一列不会有两个诸侯。求放置方案数。注意：镜面和旋转的情况属于不同的方案。

这是 $n=3$ 的图。其中第二行：第一个、第二个都不合法，第三个合法。

$n\le100$ 。

点击查看题解

题解

因为将整行或列平移并不影响诸侯间的限制关系，且题目又说了镜面和旋转的情况属于不同的方案，那我们就可以把图案平移成我们想要的样子了。

啊，这个图怎么 DP 啊？好办，把它变成下面这个就可以了：

设 $f(i,j)$ 表示已经放了 $i$ 列，且共放了 $j$ 个。

然后 DP 方程就自然地列出来了：

f(i,j)=f(i-1,j)+f(i-1,j-1)\times[len-(j-1)]

其中，第一个指的是这一列不放；第二个指的是这一列放，乘法原理，已经放 $j-1$ 个表明本行合法的放置方案数是本行长度减去 $j-1$ 。加法原理加起来，就是 $f(i,j)$ 。

最后 $f(2n-1,k)$ 就是答案。

A 掉这个题可以顺便 A 掉 https://www.luogu.com.cn/problem/P1350 （车的放置）了呀 qwq。

代码

#include<bits/stdc++.h>
using namespace std;
namespace name
{
    typedef long long ll;
    const ll N=3000+10,mod=504;
    ll n,k,f[N][N],ans[N][N];
    ll getlen(ll x){return ((x-1)/2)*2+1;}
    void main()
    {
    	scanf("%lld%lld",&n,&k);
    	for(ll i=0;i<=2*n-1;i++)
    	{
    		ll len=getlen(i);
    		f[i][0]=1;
		}
		for(ll i=1;i<=2*n-1;i++)
		{
			ll len=getlen(i);
			for(ll j=1;j<=len;j++)
			{
				f[i][j]+=f[i-1][j]; 
				f[i][j]+=f[i-1][j-1]*(len-j+1);
				f[i][j]%=mod;
			}
		}
		printf("%lld\n",f[2*n-1][k]%mod);
    	return; 
    	
    }
}
int main()
{
    name::main();
    return 0;
}