【洛谷 P9242】[蓝桥杯 2023 省 B] 接龙数列 题解(线性DP)

2024-03-18 14:12

本文主要是介绍【洛谷 P9242】[蓝桥杯 2023 省 B] 接龙数列 题解(线性DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[蓝桥杯 2023 省 B] 接龙数列

题目描述

对于一个长度为 K K K 的整数数列: A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,,AK,我们称之为接龙数列当且仅当 A i A_{i} Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai1 的末位数字( 2 ≤ i ≤ K 2 \leq i \leq K 2iK)。

例如 12 , 23 , 35 , 56 , 61 , 11 12,23,35,56,61,11 12,23,35,56,61,11 是接龙数列; 12 , 23 , 34 , 56 12,23,34,56 12,23,34,56 不是接龙数列,因为 56 56 56 的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。

现在给定一个长度为 N N N 的数列 A 1 , A 2 , … , A N A_{1},A_{2},\ldots,A_{N} A1,A2,,AN,请你计算最少从中删除多少 个数,可以使剩下的序列是接龙序列?

输入格式

第一行包含一个整数 N N N

第二行包含 N N N 个整数 A 1 , A 2 , … , A N A_{1},A_{2},\ldots,A_{N} A1,A2,,AN

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

5
11 121 22 12 2023

样例输出 #1

1

提示

【样例说明】

删除 22 22 22,剩余 11 , 121 , 12 , 2023 11,121,12,2023 11,121,12,2023 是接龙数列。

【评测用例规模与约定】

对于 20 % 20 \% 20% 的数据, 1 ≤ N ≤ 20 1 \leq N \leq 20 1N20

对于 50 % 50 \% 50% 的数据, 1 ≤ N ≤ 1 0 4 1 \leq N \leq 10^4 1N104

对于 100 % 100 \% 100% 的数据, 1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1N105 1 ≤ A i ≤ 1 0 9 1 \leq A_{i} \leq 10^{9} 1Ai109。所有 A i A_{i} Ai 保证不包含前导 0。

蓝桥杯 2023 省赛 B 组 E 题。


思路

首先定义一些变量。n是一个整数,表示输入的数列的长度。dp是一个数组,用于存储动态规划的结果,这里的dp数组存储的是以每个数字结尾的最长接龙序列的长度。

然后进入主函数。首先读取n的值。接着,使用一个循环,对于每一个输入的数,读取其值,并将其转换为字符串。然后获取该字符串的首位和末位数字,并更新dp数组。

状态转移方程:

d p [ e ] = max ⁡ ( d p [ e ] , d p [ b ] + 1 ) dp[e] = \max(dp[e], dp[b] + 1) dp[e]=max(dp[e],dp[b]+1)

这里, b b b表示当前处理的数的首位数字, e e e表示末位数字, d p [ i ] dp[i] dp[i]表示以 i i i结尾的最长接龙序列的长度。

这个状态转移方程表示,如果将当前处理的数接在以其首位数字结尾的最长接龙序列后面,可以得到一个新的以其末位数字结尾的接龙序列,其长度可能会比当前已知的以其末位数字结尾的最长接龙序列更长。因此,更新 d p [ e ] dp[e] dp[e]为两者中的较大值。

对于每一个输入的数,都会检查其首位数字对应的最长接龙序列长度加一(因为该数可以接在该序列后面),与当前末位数字对应的最长接龙序列长度,取较大的一个作为新的末位数字对应的最长接龙序列长度。

最后,遍历dp数组,找到最长的接龙序列长度。通过总长度减去最长接龙序列长度得到需要删除的最小数量,输出n减去该长度,即为需要删除的最小数量。


AC代码

#include <algorithm>
#include <iostream>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
// 以i结尾的最长接龙序列
ll dp[15];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {string s;cin >> s;int b = *s.begin() - '0';int e = *s.rbegin() - '0';dp[e] = max(dp[e], dp[b] + 1);}ll m = 0;for (int j = 0; j <= 9; j++) {m = max(m, dp[j]);}cout << n - m << "\n";return 0;
}

这篇关于【洛谷 P9242】[蓝桥杯 2023 省 B] 接龙数列 题解(线性DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/822591

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int