开元棋牌网站怎么做,如何学建设网站,dede 企业网站模板,网站微商城的建设运营实践和思考需求分析
题目要求最少删掉多少个数后#xff0c;使得数列变为接龙数列。
相当于题目要求求出数组中的最长接龙子序列。
题目分析
对于一个数能不能放到接龙数列中#xff0c;只关系到这个数的第一位和最后一位#xff0c;所以我们可以先对数组进行预处理#xff0c;将… 需求分析
题目要求最少删掉多少个数后使得数列变为接龙数列。
相当于题目要求求出数组中的最长接龙子序列。
题目分析
对于一个数能不能放到接龙数列中只关系到这个数的第一位和最后一位所以我们可以先对数组进行预处理将所有的数变为两位数例如 12345 → 15 12345 \rightarrow 15 12345→15 6 → 66 6 \rightarrow 66 6→66 … \dots …这样当我们需要取出一个数 x x x 的第一位时只需要计算 x / 10 x / 10 x/10取出最后一位时只需要计算 x % 10 x \% 10 x%10。
那么接下来考虑如何求接龙序列的最大值。
考虑动态规划 f ( i , j ) f(i, j) f(i,j) 表示在前 i i i 个数中以 j j j 结尾的最大长度。
考虑状态转移设第 i i i 个数为 a b ab ab
若不选第 i i i 个数则有 f ( i , j ) f ( i − 1 , j ) f(i, j) f(i - 1, j) f(i,j)f(i−1,j) 0 ≤ j ≤ 9 0 \leq j \leq 9 0≤j≤9。若选第 i i i 个数则 f ( i , b ) max ( f ( i − 1 , b ) , f ( i − 1 , a ) 1 ) f(i, b) \max(f(i - 1, b), f(i - 1, a) 1) f(i,b)max(f(i−1,b),f(i−1,a)1)
那么接龙数列的最大长度为 max ( { f ( n , i ) \max(\{f(n, i) max({f(n,i) 0 ≤ i ≤ 9 0 \leq i \leq 9 0≤i≤9 } ) \}) })。
观察状态转移发现 f ( i , j ) f(i, j) f(i,j) 仅由 f ( i − 1 , x ) f(i - 1, x) f(i−1,x) 计算得出故可以使用滚动数组进行优化。
时间复杂度 O ( n ) O(n) O(n)。
C
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e5 10;int n;
int q[N];
int f[N][10];int main()
{cin n;for (int i 1; i n; i ){int x;cin x;int y x % 10;while (x 10)x / 10;q[i] x * 10 y;}for (int i 1; i n; i ){for (int j 0; j 10; j )f[i][j] f[i - 1][j];int a q[i] / 10, b q[i] % 10;f[i][b] max(f[i][b], f[i - 1][a] 1);}int res 0;for (int i 0; i 10; i )res max(res, f[n][i]);cout n - res endl;return 0;
}C空间优化
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e5 10;int n;
int q[N];
int f[N];int main()
{cin n;for (int i 0; i n; i ){int x;cin x;int y x % 10;while (x 10)x / 10;q[i] x * 10 y;}for (int i 0; i n; i ){int a q[i] / 10, b q[i] % 10;f[b] max(f[b], f[a] 1);}cout n - *max_element(f, f 10) endl;return 0;
}【在线测评】
