不会dp,只能写个记忆化了(doge)
#include<bits/stdc++.h>
using namespace std;
int n,ans=1e8,dp[200][100005];
//对于当前这个下标,这条接龙的尾巴,你后面最长能接几个
int dfs(char ta,int k,int wo)//k表示长度
{
if(wo==n+1)
{
return 0;
}
if(dp[ta][wo]!=-1)return dp[ta][wo];
if(a[wo].h==ta||ta==' ')
dp[ta][wo]=dfs(a[wo].e,k+1,wo+1)+1;//可以不删
dp[ta][wo]=max(dp[ta][wo],dfs(ta,k,wo+1));
return dp[ta][wo];
}
int main()
{
memset(dp, -1, sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>st;
a[i].s=st;
a[i].h=st[0];
a[i].e=st[st.size()-1];
}
cout<<n-dfs(' ',0,1);;
}
0 回复
0 转发
1 喜欢
0 阅读



