网站开发的几种语言,公主岭网站建设,视频类网站开发经验,注册公司流程和费用大概多少钱蓝桥杯真题讲解#xff1a;接龙序列 一、视频讲解二、暴力代码三、正解代码 一、视频讲解
蓝桥杯真题讲解#xff1a;接龙序列
二、暴力代码
// 暴力代码#xff1a;DFS#xff08;2^n#xff09;
#includebits/stdc.h
#define endl \n
#define deb(x) cout 接龙序列 一、视频讲解二、暴力代码三、正解代码 一、视频讲解
蓝桥杯真题讲解接龙序列
二、暴力代码
// 暴力代码DFS2^n
#includebits/stdc.h
#define endl \n
#define deb(x) cout #x x \n;
#define INF 0x3f3f3f3f
using namespace std;
const int N 1e5 10;
int a[N];
int n, ans;int get_first(int x)//获取数字的最高位
{int res 0;while(x){res x % 10;x / 10;}return res;
}int get_final(int x)//获取数字的最后一位
{return x % 10;
}//u表示当前考虑到了第几位。
//last表示方案中已经选了的最后一个数字是多少
//cnt表示方案中一共有多少个数字
void dfs(int u, int cnt, int last)
{if(u n){ans max(ans, cnt);return;}if(n - u cnt ans){return;}//第u位数选如果选这个数字//就必须和前面最后一个数字构成接龙序列。if(last -1 || get_final(last) get_first(a[u]))dfs(u 1, cnt 1, a[u]);//第u个数不选dfs(u 1, cnt, last);
}void solve()
{cin n;for(int i 0; i n; i )cin a[i];dfs(0, 0, -1);cout n - ans endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t 1;//cin t;while(t--)solve();
}三、正解代码
//接龙序列线性DP
#includebits/stdc.h
#define INF 0x3f3f3f3f
using namespace std;
const int N 1e5 10;int f[N][15];int get_first(int x)
{int res 0;while(x){res x % 10;x / 10;}return res;
}int get_final(int x)
{return x % 10;
}void solve()
{memset(f, INF, sizeof f);int n;cin n;vectorinta(n 1);for(int i 1; i n; i )cin a[i];for(int i 0; i 10; i )f[0][i] 0;for(int i 1; i n; i ){//删除第i个数字for(int j 0; j 10; j )f[i][j] f[i - 1][j] 1;//保留第i个数字int final get_final(a[i]);int first get_first(a[i]);f[i][final] min(f[i - 1][first], f[i][final]);}int ans INF;for(int i 0; i 10; i )ans min(ans, f[n][i]);cout ans endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);int t 1;// cin t;while(t--)solve();
}
