单页面网站 万网x3,响应式公司官网建设,免费网址怎么申请注册,手机画设计图软件这道题有点难度#xff0c;是动态规划经典问题最长上升序列的变式#xff0c;需要压缩dp数组。
思路#xff1a;从题目中知道了#xff0c;数的大小其实是无所谓的#xff0c;我们只关心这个数的首位和末尾是怎么样的。显然#xff0c;如果说强力暴力分析的话#xff0…这道题有点难度是动态规划经典问题最长上升序列的变式需要压缩dp数组。
思路从题目中知道了数的大小其实是无所谓的我们只关心这个数的首位和末尾是怎么样的。显然如果说强力暴力分析的话我们会发现有多种情形然后再从这些情形当中进行筛选这是很麻烦的过程换句话说这种筛选的过程就是求最优解的过程我们就会想到用动态规划的思想。
那么对于动态规划的思想来说我们是适时进行分析的我们需要构造状态方程。那么假如我们从头开始遍历这些数字。从某个数字开始我们提取里面的首位和末尾这里我们用了两个数组l,r来实现简单来说既然DP问题都是倾向于空间换时间我们也应该也要借用这种思维少用循环的方式直接开空间存储这个时候我们想了这个dp数组应该怎么赋予含义呢
答案是dpi表示的就是以i数字为结尾的最长接龙数组个数这里的数字指的不是我们说的那种多位数字而是指我们输入的数字的其中一个数比如3455就是数字中的其中一个数字。
那么状态方程定义完了我们需要转移方程了到底该怎么转移呢这里作者认为从两头进行考虑以末尾数字为尾的最长接龙数组可以是以其首位数字为尾的最长接龙数组11是因为加上了当前的数字也可以是它本身这就跟普通的动态规划一样了就其自身和前面的最优解状态1进行取最大长度也就是
dp(back)max(dp(back),dp(front)1)front代表当前数字的首位back代表当前数字的末位
OK那么在这样之后我们就知道了这些数字中每个数字头尾的最佳接龙长度了最后取其中最大的长度就行了。
上代码
#includeiostream
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 100010
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int dp[11];
int l[MAX];
int r[MAX];
string s;
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int n;cin n;int i;for (i 1; i n; i) {cin s;l[i] s[0] - 0;r[i] s[s.size() - 1] - 0;}int res INT_MIN;for (int j 1; j n; j) {dp[r[j]] max(dp[l[j]] 1, dp[r[j]]);}for (i 0; i 10; i)res max(res, dp[i]);cout n - res endl;return 0;
}
