返回题解分享
讨论 / 题解分享/ 帖子详情

接龙数列(编程题) - 题解

不会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 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!