Blocks题解

区间dp

阅读体验。。。https://zybuluo.com/Junlier/note/1289712

很好的一道区间dp的题目(别问我怎么想到的)

dp状态

其实这个题最难的地方是这道题目的状态怎么设

首先既然是区间dp，那肯定最先想到的状态是

\(dp[i][j]\)表示消掉区间\([i,j]\)上所有的块的最大分数

突然发现这个状态会受区间外和\(i\)或\(j\)颜色相同的块的影响

并且转移也并不好转移=_=
所以我们考虑换一种状态。。。

既然说会受到外面的块的影响？那考虑一种方法来解决

\(dp[i][j][k]\)表示消掉区间\([i,j]\)并且区间\([i,j]\)右边还有k个和j颜色相同的块（除此之外，这个序列没有别的块了），消掉这些所有的块的最大分数

有点抽象，再来感性理解一下：

当前处理的子问题\(dp[i][j][k]\)主体由区间\([i,j]\)组成，然后与\(j\)相同有\(k\)块接在后面，这\(k\)块之间的其他块已经全部消完了

如果实在还不明白，先看转移吧。。。

然后可以根据我们前面的错误状态自己思考为什么加上这一维

转移

\(dp[i][j][k]\):显然有两种转移

我这里是用记忆化搜索实现的

消掉j和后面的k块

```

    dp[i][j][k]=max(dp[i][j][k],Dfs(i,j-1,0)+(k+1)*(k+1));

```

对于区间\([i,j]\)，中间可能有和\(j\)颜色相同的块，假设位置为\(p\)，我们可以选择消掉区间\([p+1,j-1]\)中所有的块使颜色拼起来，当然这是个子问题，所以前面讲了用记忆化搜索实现

PS: 下面代码的\(nxt[p]\)是预处理的在\(p\)前面第一个和\(p\)颜色相同的块的位置

```

	for(int p=nxt[j];p>=i;p=nxt[p])//枚举p

	    dp[i][j][k]=max(dp[i][j][k],Dfs(i,p,k+1)+Dfs(p+1,j-1,0));

```

汇总

讲完这些整个程序的实现就不难了

那我直接放上代码，不好意思，没有注释

#include<bits/stdc++.h>

#define lst long long

#define ldb double

#define N 250

using namespace std;

const int Inf=1e9;

int read()

{

	int s=0,m=0;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

	return m?-s:s;

}

int n;

int col[N],nxt[N],hd[N];

lst dp[N][N][N];//消掉[i,j]区间和[i,j]右边和j颜色一样的连续k个方块的最大分数

lst Dfs(int i,int j,int k)

{

	if(i>j)return 0;

	if(dp[i][j][k])return dp[i][j][k];

	dp[i][j][k]=max(dp[i][j][k],Dfs(i,j-1,0)+(k+1)*(k+1));

	for(int p=nxt[j];p>=i;p=nxt[p])

		dp[i][j][k]=max(dp[i][j][k],Dfs(i,p,k+1)+Dfs(p+1,j-1,0));

	return dp[i][j][k];

}

int main()

{

	int T=read();

	for(int tt=1;tt<=T;++tt)

	{

		n=read();

		memset(hd,0,sizeof(hd));

		memset(dp,0,sizeof(dp));

		memset(nxt,0,sizeof(nxt));

		for(int i=1;i<=n;++i)

		{

			col[i]=read();

			nxt[i]=hd[col[i]];

			hd[col[i]]=i;

		}

		printf("Case %d: %lld\n",tt,Dfs(1,n,0));

	}

	return 0;

}

巴特西

Blocks题解(区间dp)

Blocks题解

区间dp

dp状态

转移

汇总

最新文章

热门文章