首页 > 其他分享 >P1006 [NOIP2008 提高组] 传纸条(线性 dp)

P1006 [NOIP2008 提高组] 传纸条(线性 dp)

时间:2024-08-02 13:28:57浏览次数:15  
标签:状态 P1006 路径 NOIP2008 重合 两条 re dp

link

真的,第一次听懂了 闫氏dp分析法,从集合的角度分析

首先,两条路径,很朴素的状态表示就是定义 \(f[x_1,y_1,x_2,y_2]\) 来表示两条路径分别走到当前点的最大值

但是,这样状态数量就达到了 6.25e7,有点极限

tip:动态规划的时间复杂度一般可以表示为 状态数量与状态计算量的乘积

注意到题意等价于两条路径从 (1, 1) 同时出发,不重复点,到达 (n, m)

发现任意时刻,\(x_1 + y_1 = x_2 + y_2\) ,那么我们可以定义一个随时间变化的量 \(k\) 表示横纵坐标之和(总步数),那么纵坐标就可以表示为 \(k - x\),状态即 \(f[k,x_1,x_2]\)

观察性质 消元应该算吧),状态量就从 \(n^4\) 降到 \(2n^3\)

综上谓之 状态表示 \(f[k,x_1,x_2]\)

  • 集合:所有两条路径从 (1, 1) 分别走到 (x1, k - x1)、(x2, k - x2) 的路线组合的集合

  • 属性:最大值


接下来就是 状态计算

题目说当前状态 (x, y) 只能从 (x, y - 1) 或 (x - 1, y) 转移

两条路径,就有四种情况,分而治之,把集合分成四块分别讨论,

tip:状态划分的依据一般是找到最后一个不同点

image

对于当前点的贡献需要特别分析,依据题意,两条路径不能重合,也就是说一个点最多只能算一次贡献。所以,若两条路径在当前点重合,我就只算一次贡献,反之两次贡献

虽然这样分析,把重合这种非法情况包括进来了,但是显然重合累加一次贡献一定小于不重合累加两次,所以一定会被更优解更新掉,也就没什么影响啦。

时间复杂度为 \(O(2n\cdot n^2 \cdot 4)\),即 \(O(n^3)\)

#include <bits/stdc++.h>
#define re register int 

using namespace std;
const int N = 55;

int n, m, w[N][N], f[N << 1][N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= m; j ++) cin >> w[i][j];
	
	for (re k = 2; k <= n + m; k ++)
		for (re x1 = max(1, k - m); x1 <= min(k - 1, n); x1 ++)
			for (re x2 = max(1, k - m); x2 <= min(k - 1, n); x2 ++)
			{
				int t = (x1 != x2 ? w[x1][k - x1] + w[x2][k - x2] : w[x1][k - x1]);
				
				for (re a = 0; a <= 1; a ++)
					for (re b = 0; b <= 1; b ++)
						f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t);
			}
	cout << f[n + m][n][n] << '\n';
	
	return 0;
}

标签:状态,P1006,路径,NOIP2008,重合,两条,re,dp
From: https://www.cnblogs.com/wenzieee/p/18338496

相关文章

  • profibus DP 使用半双工的485物理层为什么可以支持多个主站
    profibusDP使用半双工的485物理层为什么可以支持多个主站 PROFIBUSDP(DecentralizedPeripherals)是一个用于工业自动化的高速现场总线协议,广泛用于连接各种设备如传感器、执行器和控制器。PROFIBUSDP使用了RS-485物理层来实现数据传输。RS-485是一......
  • android 音频播放器,(一)SoundPool音频播放实例
    1.Apk内,预定义按键与触发按键:layout按键定义:  <Button    android:id="@+id/start"    android:layout_width="match_parent"    android:layout_height="wrap_content"    android:textAllCaps="false"    an......
  • HT-018 Div3 能量消耗 题解 [ 绿 ] [ 线性 dp ] [ 前缀和优化 ]
    能量消耗:一个前缀和优化dp的大典题,要是数据水一点\(O(n^3)\)都能硬草过去。思路显然,定义\(dp[i]\)为考虑前\(i\)个塔,并且将前面的精灵全部收集的最小代价。于是转移:\[dp[i]=min(dp[i],dp[j]+w(j,i)+c[i])\]其中\(0\lej<i\lem\),\(w(j,i)\)表示收集从塔\(j\)到......
  • wordpress 修改后台密码
    1、数据库修改登录数据库,执行以下命令就可以,执行后就可以使用123456登录UPDATEwp_usersSETuser_pass='$1$rSziHLDY$399k.JuJsy.oHVp5lquJC.'WHEREuser_login='root';注意:这里的账号是root,知道自己账号的可以更改为自己的账号为确保起见,不知道账号的可以先查询,......
  • 背包DP
    背包DP是线性DP中一种特殊的DP。01背包最基础的背包,有\(n\)件物品,背包容量为\(V\),每件物品只有一件。可以使用空间优化,一般是原地滚动,此时注意容量需要从后往前更新,否则会一个状态更新多次。时间复杂度为\(O(nV)\)。核心代码voidsolve(){intn,V;cin>>n>>......
  • 状压DP
    状压DP(BitmaskDP)将状态压缩为二进制表示,用于处理状态复杂的问题。主要分为一维和二维两种类型。一维状压DP最经典的是求最短哈密顿路径,对应\(n\)个结点的带权无向图,暴力枚举所有情况的时间复杂度为\(O(n)\),但是我们思考一下,到达某个顶点时,需要记录在这之前已经走过结点是......
  • Luogu P1613 跑路 题解 [ 蓝 ] [ 倍增 ] [ Floyd 最短路 ] [ 状压 dp ]
    跑路:绝佳倍增好题,思路是化\(2^k\)为\(1\),倍增起预处理作用。最近不知道是撞了什么运,前一脚看的是绿题,写完之后交一发,发现直接被lxl升蓝了,血赚。思路:Floyd首先观察到每次走\(2^k\)的代价为\(1\),我们可以预处理出每次走\(2^i\)能到哪些点。但为了让这题的代码更好实......
  • 为什么 DDoS 攻击偏爱使用 TCP 和 UDP 包?
    DistributedDenialofService(DDoS)攻击是指攻击者利用多个计算机系统或网络设备(通常是被恶意软件感染的计算机,被称为“僵尸网络”)来淹没目标服务器的资源,导致合法用户无法访问服务。TCP和UDP是两种最常见的用于DDoS攻击的网络协议。1.TCP和UDP的特性TCP(Tr......
  • 在AWS Lightsail建立WordPress Multisite & Route 53 subdomains & Hexo Blog & WordP
    1.0前言玩Startup比賽,因需高效快速地做POC原型產品,所以利用AWS云端服務來更快地開發。你會學到:LightSail建立WordpressmultisiteRoute53註冊WordpressSubdomains&GithubCuostomDomainLightSailCustomDomain&SSLHexo快速搭建GihubPages博客+ Route53 Custom......
  • Codeforces 11D A Simple Task 题解 [ 蓝 ] [ 状压 dp ]
    思路不难想,细节比较多。思路观察到\(n\le19\),首先想到状压dp。于是自然地定义\(dp[j][i]\)为:抵达点的状态为\(i\),且此时在点\(j\)时,简单路径的条数。注意这里是简单路径的条数,而不是环的个数,因为环的个数要在dp过程中统计。这里的dp作用就在于求简单路径条数。......