算法自学__线性动态规划

这篇具有很好参考价值的文章主要介绍了算法自学__线性动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

例1 P1020 [NOIP1999 普及组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度,计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行,若干个整数,中间由空格隔开。

输出格式

两行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

389 207 155 300 299 170 158 65

样例输出 #1

6
2

提示

对于前 50 % 50\% 50% 数据(NOIP 原题数据),满足导弹的个数不超过 1 0 4 10^4 104 个。该部分数据总分共 100 100 100 分。可使用 O ( n 2 ) \mathcal O(n^2) O(n2) 做法通过。
对于后 50 % 50\% 50% 的数据,满足导弹的个数不超过 1 0 5 10^5 105 个。该部分数据总分也为 100 100 100 分。请使用 O ( n log ⁡ n ) \mathcal O(n\log n) O(nlogn) 做法通过。

对于全部数据,满足导弹的高度为正整数,且不超过 5 × 1 0 4 5\times 10^4 5×104

思路

这道题目实质上就是考察最长不上升子序列最长上升子序列的求法,以前者为例。

定义tail1[i],表示:长度i的不上升子序列的最后一个元素的值。显然,tail1[]数组是单调不升的。定义cnt1表示当前最长不上升子序列的长度。我们从头至尾遍历输入的每一个元素,如果当前元素:

  • ≤ \leq tail1[cnt1],说明当前元素可以直接添加到目前的最长不上升子序列的末尾,形成一个更长的子序列。
  • > > > tail1[cnt2],我们二分查找到tail1[]数组中第一个小于当前元素的值tail1[i],并将其修改为当前元素。首先,这样做是可行的,因为tail1[i-1] 一定 ≥ \ge 当前元素,所以将当前元素接在一个长度为i-1的不上升子序列的结尾,可以形成一个长度为i的不上升子序列,符合tail1[]数组的定义。其次,这样做是合理的,因为在一个不上升子序列中,位于前面的元素越大,这个子序列便可能越长。

遍历输入的所有元素后,cnt1的值即为最长不上升子序列的长度。

代码

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int a[maxn];
int n = 0;
int tail1[maxn];
int tail2[maxn];
int cnt1=0, cnt2=0;

int main(){
	int temp;
	while(cin>>temp){
		n++;
		a[n] = temp;
	}
	tail1[0] = 0x7f7f7f7f;
	tail2[0] = -1;
	for(int i=1;i<=n;i++){
		if(a[i]<=tail1[cnt1]){
			cnt1++;
			tail1[cnt1] = a[i];
		}
		else{
			int L=1, R=cnt1, pos=0;
			while(L<=R){
				int mid = (L+R)>>1;
				if(tail1[mid]<a[i]){
					pos = mid;
					R = mid-1;
				}
				else{
					L = mid+1;
				}
			}	
			tail1[pos] = a[i];
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]>tail2[cnt2]){
			cnt2++;
			tail2[cnt2] = a[i];
		}
		else if(a[i]==tail2[cnt2]){
			continue;
		}
		else{
			int L=1, R=cnt2, pos=0;
			while(L<=R){
				int mid = (L+R)>>1;
				if(tail2[mid]>=a[i]){
					pos = mid;
					R = mid-1;
				}
				else{
					L = mid+1;
				}
			}
			tail2[pos] = a[i];
		}
	}
	cout<<cnt1<<'\n'<<cnt2;
	return 0;
}

例2 P2679 [NOIP2015 提高组] 子串

题目描述

有两个仅包含小写英文字母的字符串 A A A B B B

现在要从字符串 A A A 中取出 k k k 个互不重叠的非空子串,然后把这 k k k 个子串按照其在字符串 A A A 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 B B B 相等?

注意:子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数 n , m , k n,m,k n,m,k,分别表示字符串 A A A 的长度,字符串 B B B 的长度,以及问题描述中所提到的 k k k,每两个整数之间用一个空格隔开。

第二行包含一个长度为 n n n 的字符串,表示字符串 A A A

第三行包含一个长度为 m m m 的字符串,表示字符串 B B B

输出格式

一个整数,表示所求方案数。

由于答案可能很大,所以这里要求输出答案对 1000000007 1000000007 1000000007 取模的结果。

样例 #1

样例输入 #1

6 3 1 
aabaab 
aab

样例输出 #1

2

提示

对于第 1 组数据: 1 ≤ n ≤ 500 , 1 ≤ m ≤ 50 , k = 1 1≤n≤500,1≤m≤50,k=1 1n500,1m50,k=1;
对于第 2 组至第 3 组数据: 1 ≤ n ≤ 500 , 1 ≤ m ≤ 50 , k = 2 1≤n≤500,1≤m≤50,k=2 1n500,1m50,k=2;
对于第 4 组至第 5 组数据: 1 ≤ n ≤ 500 , 1 ≤ m ≤ 50 , k = m 1≤n≤500,1≤m≤50,k=m 1n500,1m50,k=m;
对于第 1 组至第 7 组数据: 1 ≤ n ≤ 500 , 1 ≤ m ≤ 50 , 1 ≤ k ≤ m 1≤n≤500,1≤m≤50,1≤k≤m 1n500,1m50,1km;
对于第 1 组至第 9 组数据: 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 100 , 1 ≤ k ≤ m 1≤n≤1000,1≤m≤100,1≤k≤m 1n1000,1m100,1km;
对于所有 10 组数据: 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 200 , 1 ≤ k ≤ m 1≤n≤1000,1≤m≤200,1≤k≤m 1n1000,1m200,1km

思路

定义状态f[i][j][k]表示:在字符串a的前i个字符中任意选取k个子串,且必须选择a[i],能拼出字符串b的前j个字符构成的子串的方案数

定义状态g[i][j][k]表示:在字符串a的前i个字符中任意选取k个子串,a[i]可选可不选,能拼出字符串b的前j个字符构成的子串的方案数

状态转移方程一:
f [ i ] [ j ] [ k ] = { f [ i − 1 ] [ j − 1 ] [ k ] + g [ i − 1 ] [ j − 1 ] [ k − 1 ] , a [ i ] = = b [ j ] 0 , a [ i ]   ! = b [ j ] f[i][j][k] = \begin{cases} f[i-1][j-1][k] + g[i-1][j-1][k-1], &a[i]==b[j]\\ 0, &a[i]\ !=b[j] \end{cases} f[i][j][k]={f[i1][j1][k]+g[i1][j1][k1],0,a[i]==b[j]a[i] !=b[j]
解释:当a[i]b[i]不相等时,f[i][j][k]显然为0。当a[i]b[i]相等时,a[i]要么和别的字符共同构成一个子串,要么自己单独构成一个子串。和别的字符共同构成一个子串的情形,对应f[i-1][j-1][k],即a[i]添加到了a[i-1]所在子串的末尾;单独构成一个子串的情形,对应g[i-1][j-1][k-1],即前面选出k-1个子串,构成b[1]~b[j-1]的部分。

状态转移方程二:
g [ i ] [ j ] [ k ] = f [ i ] [ j ] [ k ] + g [ i − 1 ] [ j ] [ k ] g[i][j][k] = f[i][j][k] + g[i-1][j][k] g[i][j][k]=f[i][j][k]+g[i1][j][k]
解释:根据g[i][j][k]的定义,a[i]要么选,要么不选。选的情形,对应f[i][j][k];不选的情形,对应g[i-1][j][k]文章来源地址https://www.toymoban.com/news/detail-407657.html

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1005;
const int maxm = 205;
const int p = 1000000007;

int f[2][maxm][maxm];
int g[2][maxm][maxm];
int cnt = 0;
int n, m, K;
char a[maxn], b[maxm];

int main(){
	cin>>n>>m>>K;
	//让字符串从下标1开始
	cin>>a+1>>b+1;
	//保证(a[i]==b[j])为真,且j为1、k为1时,f[cnt][j][k]为1
	g[0][0][0] = g[1][0][0] = 1;
	//滚掉i
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(m, i);j++){
			for(int k=1;k<=K;k++){
				if(a[i]==b[j]){
					f[cnt][j][k] = (f[cnt^1][j-1][k]+g[cnt^1][j-1][k-1]) % p;
				}
				else{
					f[cnt][j][k] = 0;
				}
				g[cnt][j][k] = (g[cnt^1][j][k]+f[cnt][j][k]) % p;
			}
		}
		cnt = cnt^1;
	}
	cout<<g[cnt^1][m][K];
	return 0;
}

到了这里,关于算法自学__线性动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • [NOIP2002 普及组] 选数#洛谷

    已知 n n n 个整数 x 1 , x 2 , ⋯   , x n x_1,x_2,cdots,x_n x 1 ​ , x 2 ​ , ⋯ , x n ​ ,以及 1 1 1 个整数 k k k ( k n kn k n )。从 n n n 个整数中任选 k k k 个整数相加,可分别得到一系列的和。例如当 n = 4 n=4 n = 4 , k = 3 k=3 k = 3 , 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3 , 7 , 12 , 19 时,

    2024年01月20日
    浏览(45)
  • 一本通1919:【02NOIP普及组】选数

    这道题感觉很好玩。 先放题目: 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.php?pid=1919 已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,

    2024年02月16日
    浏览(34)
  • [NOIP2007 普及组] 纪念品分组

    元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间

    2024年02月14日
    浏览(44)
  • NOIP2003普及组复赛T2:数字游戏

    题目链接:NOIP2003普及组复赛T2 - 数字游戏 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共 n n n 个),你要按顺序将其分为 m m m 个部分

    2024年02月09日
    浏览(40)
  • [NOIP2004 普及组] FBI 树 队列解法

    我们可以把由 0 和 1 组成的字符串分为三类:全 0 串称为 B 串,全 1 串称为 I 串,既含 0 又含 1 的串则称为 F 串。 FBI 树是一种二叉树,它的结点类型也包括 F 结点,B 结点和 I 结点三种。由一个长度为 $2^N$ 的 01 串 S 可以构造出一棵 FBI 树 T,递归的构造方法如下: 1. T 的根

    2024年02月07日
    浏览(90)
  • #P0999. [NOIP2008普及组] 排座椅

    上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 DD 对同学上课时会交头接耳。 同学们在教室中坐成了 MM 行 NN 列,坐在第 ii 行第 jj 列

    2024年02月15日
    浏览(44)
  • P1077 [NOIP2012 普及组] 摆花 题解

    小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m m m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n n n 种花,从 1 1 1 到 n n n 标号。为了在门口展出更多种花,规定第 i i i 种花不能超过 a i a_i a i ​ 盆,摆花时同一种花放在一起,且不同种类的花

    2024年02月08日
    浏览(45)
  • 搜索?——P3956 [NOIP2017 普及组] 棋盘

    传送门: [NOIP2017 普及组] 棋盘 - 洛谷 思路: 将棋盘的每一个格子看做一个点,建一个无向图用来跑最短路. 这道题本应用搜索来做,但是转换成最短路好像简单点 建图: 1.对于已经有颜色的格子,在扫描四个方向的格子对相同颜色的建条长度为0的边,不同颜色的建条长度为1的

    2024年02月01日
    浏览(35)
  • #P1003. [NOIP2009普及组] 道路游戏

    小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 nn 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 nn 个机器人工厂编号为 1sim n1∼n,因为马路是环形的,所以第 nn 个机器人工厂和

    2024年02月15日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包