Partition:一道 dp 神题,用到了以轮廓线的轨迹来做 dp 的技巧,和敲砖块这题的状态设计有点相似。
观察
首先观察样例,发现整张图可以看作是被两条线分隔开的。同时每个颜色的四个方向上又存在一大堆奇怪的性质,很容易发现这两条线一条是从左上到右下的线,另一条是从右下到左上的线。
暴力 dp
有了这两条线,并且发现这两条线一定不会往回走(比如往上走的线,不会在某个地方往下走),即无后效性,那么我们就可以暴力 dp 了。
设计 \(dp_{i,j,k}\) 表示在第 \(i\) 行时,两条线分别在第 \(j\) 列与第 \(k\) 列时的最大值。
然后暴力转移一下就好了,这种做法还要对两条线的位置关系进行分讨转移,比较麻烦,复杂度又高,因此我们需要从另一个角度考虑 dp。
正解
我们观察每个颜色各自的贡献,可以发现,红色的权值为 \(1\),且其他颜色的权值都比 \(1\) 大。因此我们可以把染色的过程看作先把每个数涂上红色,然后其他颜色的权值减小了 \(1\),再来 dp。
这样以后橙色的权值为 \(1\),黄色的权值为 \(2\),绿色的权值为 \(3\)。再来观察图的形态,可以发现橙色和绿色是连在一起的。所以我们可以把橙色和绿色的部分统一先填上色,过程就和上面暴力 dp 一样,从右上到左下进行 dp,只不过我们只需要维护一条线的路线,复杂度降低了很多。
从右上到左下具体的转移方程如下:
\[dp_{i,j}=\max(dp_{i-1,j}+f_{i,m}-f_{i,j-1},dp_{i,j+1}+a_{i,j}) \]其中 \(f_{i,j}\) 表示第 \(i\) 行的前缀和数组,\(a_{i,j}\) 表示第 \(i\) 行第 \(j\) 列的元素。
最后黄色和绿色的权值都变成 \(2\) 了,因为他们两个依然是相邻的,所以我们可以从左上到右下做一次 dp,做最后一次涂色,统计进答案就好了。
一共做了两次 dp,时间复杂度为 \(O(nm)\)。
代码
在实现上我们在 dp 时可以多进行一次,这样统计答案时就不用一个一个取最大值,只需要取最后转移到的地方就好了。
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m;
ll a[2005][2005],dp1[2005][2005],dp2[2005][2005],ans=0,f[2005][2005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
ans+=a[i][j];
f[i][j]=f[i][j-1]+a[i][j];
}
}
memset(dp1,-0x3f,sizeof(dp1));
memset(dp2,-0x3f,sizeof(dp2));
for(int i=1;i<=m+1;i++)dp1[0][i]=dp2[0][i]=0;
for(int i=1;i<=n+1;i++)
{
for(int j=m+1;j>=1;j--)
{
dp1[i][j]=max(dp1[i-1][j]+f[i][m]-f[i][j-1],dp1[i][j+1]+a[i][j]);
}
for(int j=1;j<=m+1;j++)
{
dp2[i][j]=max(dp2[i-1][j]+f[i][j-1],dp2[i][j-1]+a[i][j-1]);
}
}
cout<<ans+dp1[n+1][1]+2*dp2[n+1][m+1];
return 0;
}
标签:dp1,int,题解,Partition,Luogu,权值,2005,两条线,dp
From: https://www.cnblogs.com/zhr0102/p/18388630