ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客小白月赛]D - 造桥(思维 + DP)

2022年4月10日 1057点热度 0人点赞 0条评论

题目传送门:D-造桥_牛客小白月赛47 (nowcoder.com)

题目大意请看原题。

思路

每一个零件相当于一条边,边权为字符串长度,起点是第一个字符,终点为最后一个字符。

我们用dp[i]表示以字符i结尾所能得到的最长的桥的长度,那么就有状态转移方程:

全部更新完成之后,从dp['a'] ~ dp['z']中选出最大输出的即可。

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int dp['z' + 1];

void solve()
{
	memset(dp, 0, sizeof dp);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)
	{
		string s;cin >> s;
		dp[s.back()] = max(dp[s.back()], (int)s.size() + dp[s.front()]);
	}
	int ans = 0;
	for(char ch = 'a';ch <= 'z'; ++ ch)ans = max(ans, dp[ch]);
	cout << ans << '\n';
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP 思维 牛客网 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号