开头扯蛋

DP的骚操作太多了，和

线段树一样。

因此本文带你看一些dp好题。

正文部分

一.普通的 DP

LCS/LIS问题

LIS

原来的 $f[i]$ 表示的是$ [1,i] $的LIS

现在改一下，用$ f[i] $ 表示长度为 $i$ 的LIS 最后结尾的最小值。

此时贪心，i从前向后枚举。

加上一个当前长度的变量k

$A$ 为原来的数组

构造出以下代码

getplace是指找 $f$ 中第一个大于等于 $a[i]$ 的位置

int a[],f[]; 
	register int i,j;
	int k=1;
	f[1]=a[1];
	for(i=1;i<=n;i++)
	{
		if(f[k]<a[i]) f[++k]=a[i];
		else f[getplace(a[i])]=a[i];
	}

LCS

和LIS的处理很像，只需要加一个标记数组map

$map[a[i]] $指向 $a[i] $ 在 a的位置 (听起来很傻)

然后就可以用 $map[b[i]]$ 来表示LIS代码中的 $A$

int a[],b[],f[],map[];
	register int i,j;
	for(i=1;i<=n;i++) map[a[i]]=i;
	int k=1;
	f[1]=map[b[1]]; 	
	for(i=1;i<=n;i++)
	if(map[b[i]]>f[k]) f[++k]=map[b[i]];
	f[getplace(map[b[i]])]=map[b[i]];

LCIS

我的上一篇博客给的很清楚，这里不再赘述

DP学习记

注意事项

二分其实是不一样的，比如这里的getplace 求的大于等于 $X$ 的 $f$ 中的第一个位置，写成代码应该是这样

总之求小于等于的时候是返回r，大于等于的时候范围l，定值的时候返回mid(有时候题目会要求返回-1)

方格上的DP

P1006 传纸条

N^4 做法

$f [i] [j] [k] [l]$ 表示第一个点走到 $( i,j )$ 第二个点走到k,l的价值最大值。

显然可以得到一个dp方程

其中$a [i] [j] $表示原来方格上面的$ ( i,j )$号位置的数字。

1	f[i][j][k][l]=max(max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]),max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]))+a[i][j]+a[k][l];

此外，为了防止枚举的时候出现重复情况，枚举 $( k,l )$ 的时候l 要从j+1的位置开始向右枚举

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

using namespace std;

int n,m,f[51][51][51][51];
int a[51][51];

int main()
{
	ios::sync_with_stdio(false);
	int i,j,k,l;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++) cin>>a[i][j];
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(k=1;k<=n;k++)
	for(l=j+1;l<=m;l++)
	f[i][j][k][l]=max(max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]),max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]))+a[i][j]+a[k][l];
	cout<<f[n][m-1][n-1][m];
	return 0;
}

N^3 做法

参考八皇后问题，这里不再给出，可以去看洛谷这道题的题解。

棋盘制作

悬线法好题，考自对悬线法的理解。

悬线法一般都求的是最全为0或1的矩形，可这里要求的是0101的矩形

其实改一下判断就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int up[1100][1100],l[1100][1100],r[1100][1100];
int n,m,mp[1100][1100],ans1,ans2;

inline void getlr()
{
	register int i,j;
	for(i=1;i<=n;i++)
	for(j=2;j<=m;j++)
	{
		if(mp[i][j]!=mp[i][j-1]) l[i][j]=l[i][j-1];
	}
	for(i=1;i<=n;i++)
	for(j=m-1;j>=1;j--)
	{
		if(mp[i][j]!=mp[i][j+1]) r[i][j]=r[i][j+1];
	}
	return ;
}

inline void dp()
{
	register int i,j;
	register int ans=0;
	for(i=2;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		if(mp[i][j]!=mp[i-1][j])
		{
			l[i][j]=max(l[i-1][j],l[i][j]);
			r[i][j]=min(r[i-1][j],r[i][j]);
			up[i][j]=up[i-1][j]+1; 
		}
		int a,b;
		a=(r[i][j]-l[i][j]+1);
		b=min(a,up[i][j]);
		ans1=max(ans1,(r[i][j]-l[i][j]+1)*up[i][j]);
		ans2=max(ans2,b*b);
        //ans1求的是矩形，ans2求的是正方形
	}
	return ;	
}

int main()
{
	int i,j;
	scanf("%d %d\n",&n,&m);
	char t;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		scanf("%d",&mp[i][j]);
		l[i][j]=j;
		r[i][j]=j;
		up[i][j]=1;
	}
	getlr();
	dp();
	printf("%d\n%d",ans2,ans1);
}

二.区间DP

带有边界的DP

关路灯

普通的dp: $f [i] [j] [k] 表示人关了$ [i,j] $的灯后所处的位置

但是仔细一想，貌似 k只有在左右边界的时候才会有最优情况，而且可以通过其他地方转移而来。

不得不说想到这种解法的人真的巨，空间复杂度低了很多，时间复杂度也优化了一维

for(l=2;l<=n;l++)
	for(i=1;i+l<=n+1;i++)
	{
		j=i+l-1;
		f[i][j][0]=min(f[i+1][j][1]+jl[i][j]*g[i+1][j],f[i+1][j][0]+jl[i+1][i]*g[i+1][j]);
		f[i][j][1]=min(f[i][j-1][1]+jl[j][j-1]*g[i][j-1],f[i][j-1][0]+jl[i][j]*g[i][j-1]);
	}

全部代码


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int f[60][60][20],g[60][60],jl[60][60];
int place[60];
int cost[60];
int n,st,mmn=0x3f3f3f3f,tot;

int main()
{
	int i,j,k,l;
	scanf("%d %d",&n,&st);
	memset(f,0x3f,sizeof(f));
	f[st][st][0]=0;
	f[st][st][1]=0;
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&place[i],&cost[i]);
		tot+=cost[i];
	}
	for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	g[i][j]=g[i][j-1]+cost[j];
	for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	{
		g[i][j]=tot-g[i][j];
		
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	jl[i][j]=abs(place[i]-place[j]);
	for(l=2;l<=n;l++)
	for(i=1;i+l<=n+1;i++)
	{
		j=i+l-1;
		f[i][j][0]=min(f[i+1][j][1]+jl[i][j]*g[i+1][j],f[i+1][j][0]+jl[i+1][i]*g[i+1][j]);
		f[i][j][1]=min(f[i][j-1][1]+jl[j][j-1]*g[i][j-1],f[i][j-1][0]+jl[i][j]*g[i][j-1]);
	}
	mmn=min(f[1][n][0],f[1][n][1]);
	printf("%d",mmn);
}