暴力代码,只能过1/5的测试用例 ,不能ac
决策树:
#include<vector>
#include<string>
#include<iostream>
#define int long long
using namespace std;
//最大保留多少个数(maxv) ,使剩下的序列是接龙序列
//最少从中删除多少个数 = 总数-maxv
int GetFirst(int x)
{
string s;
s = to_string(x);
return s[0] - '0';
}
int GetLast(int x)
{
string m;
m = to_string(x);
return m[m.size() - 1] - '0';
}
vector<int> path;
int ret = 0;
//last表示上一次dfs的最后一个数字
void DFS(vector<int>& v, int i, int count, int last ) // count 表示已经选了几个数字, i选到了第几位
{
if (i == v.size())
{
ret = max(ret, count);
return;
}
//选第i个数
// 34的末位== 56的首位
if (last==-1 ||GetLast(last) == GetFirst(v[i]))
{
path.push_back(v[i]);
DFS(v, i + 1, count + 1,v[i] );
//回溯
path.pop_back();
}
//不选第i个数
DFS(v, i + 1, count, last);
}
signed main()
{
int N = 0;
cin >> N;
vector<int> v(N, 0);
for (int i = 0; i < N; i++)
{
cin >> v[i];
}
//path.resize(N, 0);
DFS(v,0,0,-1);
cout << N - ret;
return 0;
}
path数组,是用来调试,看数据的,可以不写