2019.8.29刷题统计

今天是连续打卡的第53天。

9月1日47中期初考试,这几天需要复习,刷题数量可能会略有减少,但不会间断(保证每天刷题)

第一题:1169

这道题似乎是ZJOI2007的题。(当年浙江省选难度竟然才蓝题到紫题?)

在洛谷上参考了题解的思路(保证没有抄袭代码),查题解是由于没理解下面提示中“题目就变成了求图中最长链及最长链个数”这句话以及没看懂“f[i]就等于连到i且满足距离等于起点到i的临时最长距离的点的f之和”这句话(现在都已经明白了)。

这道题是真正发挥了Tarjan求强连通分量和拓扑排序两个算法的作用,之前的题目都接近于模板,只有这道题是通过这两个算法对图做处理后再进行DP算法的。

正是因为如此,这道题代码量也很大(对于省选题来说,其实也还不算大),超过2K。

令我感到奇怪的是:这道题在写代码时没有遇到什么困难,而且交一遍就过了!

AC代码:

 

 

 

 明天计划:完成1170、1171两道题

原文地址:https://www.cnblogs.com/wangximing/p/11432497.html