首页 > 其他分享 >Luogu P10997 Partition 题解 [ 蓝 ] [ 轮廓 dp ]

Luogu P10997 Partition 题解 [ 蓝 ] [ 轮廓 dp ]

时间:2024-08-30 18:36:48浏览次数:12  
标签:dp1 int 题解 Partition Luogu 权值 2005 两条线 dp

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

相关文章

  • CF603E 题解
    题意给定一个\(n\)个结点的无向图,初始没有边。接下来有\(m\)个询问,每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后,查询是否存在一个边集\(E\),满足当图中只有\(E\)中的边时,所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}......
  • 【Mysql】mysql count主键字段很慢超时 执行计划Select tables optimized away ,最终调
     背景: mysql表 主键字段count,速度很慢,耗时将近30s   从执行计划可以看出:explainSELECTCOUNT(rule_id)ASdataCountFROM`sku_safe_stock_rule`;   原理分析:SelecttablesoptimizedawaySELECT操作已经优化到不能再优化了(MySQL根本没有遍历......
  • CF891E Lust 题解
    题目链接点击打开链接题目解法会不了\(egf\)/ll我们把贡献变成\(\prod\limits_{j\neqi}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n(a_i-[i=j])\)即答案为一开始的乘积\(-\)\(k\)次操作之后所有数乘积的期望因为有顺序,所以用\(egf\)的形式表示最后乘积的期......
  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer题解
    没什么废话、超级珂爱的大模拟。本蒟蒻写了2h才过。其实就是按题意模拟即可,不需要什么高深的算法。本人就是错在了符号中的“=”,因为如果是连续的两个等于号,只能输出“==”,而不能输出“=”“==”,然后本人就卡在这个地方卡了1.5h。代码量也不大,主要是毒瘤细节模拟题。......
  • P6192 【模板】最小斯坦纳树 题解
    Description给定一个包含\(n\)个结点和\(m\)条带权边的无向连通图\(G=(V,E)\)。再给定包含\(k\)个结点的点集\(S\),选出\(G\)的子图\(G'=(V',E')\),使得:\(S\subseteqV'\);\(G'\)为连通图;\(E'\)中所有边的权值和最小。你只需要求出\(E'\)中所有边的权值......
  • BZOJ 4403序列统计题解
    缅怀zxc......
  • CSP-J 2021 初赛试题解析(第三部分:完善程序(2))
    完善程序二完整程序代码#include<iostream>usingnamespacestd;structpoint{intx,y,id;};boolequals(pointa,pointb){returna.x==b.x&&a.y==b.y;}boolcmp(pointa,pointb){returna.x!=b.x?a.x<b.x:a.y<b.y;}......
  • luoguP5369 [PKUSC2018] 最大前缀和
    题目n<=20题解想了半天3位状态的折半,然后发现空间开不下(时间也不太行)所以放弃思考,直接枚举答案答案是a中的一个集合,设为S;记集合S的和为sum[S]考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部......
  • AT_arc170_b 的题解
    (一)因为\(a_i\)较小,那么可以对每一个\(i\),求出它右边离他最近的值为\(j\)的位置。枚举左端点和中间那个数\(a_j\),那么可以求出最小的\(k\)。这样就求出了每个左端点可以取到的最小的\(k\),记为\(b_i\)再从右到左\(b_i=\min(b_i,b_{i+1})\)。(二)AC代码。#include<bi......
  • AGC041D Problem Scores 题解
    在分值不降的条件下,要使任意一个大小为\(k\)的子集\(S\)内题目的分值之和少于任意一个大小为\(k+1\)的子集\(T\)内题目的分值之和,容易发现只需要取\(S\)为后\(k\)道题目,\(T\)为前\(k+1\)道题目时满足限制即可。换而言之,只需要对满足\(a\)的每一段长为\(k+......