如何做网站吸引广告商,网站空间的地址,淘宝客网站WordPress,关于网站开发的题目描述
对于一个长度为 K 的整数数列#xff1a;A1, A2, . . . , AK#xff0c;我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列#xff1b;12, 23, 34, 56 不是接龙数列#xff0c;因为 …题目描述
对于一个长度为 K 的整数数列A1, A2, . . . , AK我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列12, 23, 34, 56 不是接龙数列因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1, A2, . . . , AN请你计算最少从中删除多少个数可以使剩下的序列是接龙序列
思路
能想到dp就基本上知道咋写了。
dp[i]表示以选第i个数所能够构成的最长序列。st表示第i个数的开头的数字ed表示第i个数的结尾的数字。
则dp[i]max{dp[前面以st结尾的数字]}。
优化可以记录每个字母的最大结尾的长度每次更新只需要考虑ed即可。
代码
#includebits/stdc.h
using namespace std;int dp[100005];
vectorstringstr;
int main(){int n;cinn;for(int i0;in;i){string s;cins;str.push_back(s);}dp[0]1;int mx[10]{0};int ans0;for(int i0;in;i){int ststr[i].front()-0;int edstr[i].back()-0;dp[i]mx[st]1;if(dp[i]mx[ed]){mx[ed]dp[i];}ansmax(ans,dp[i]);}coutn-ans;}
