相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5772
神犇题解:http://www.cnblogs.com/qscqesze/p/5715939.html
解题报告
日常看错题系列:
- 子序列看成子串
- 值域范围$0 \sim 9$看漏
于是只会跑$n$遍网络流的算法了 QwQ
大概就是枚举左端点,然后暴力跑
考虑原题的话,唯一的Trick就是如何处理一个数第一次选的代价不同
我们可以使用最大权闭合子图来解决这个问题:
每一类数字新建一个结点,权值为$b_i – a_i$
值为该数字的所有序列上的点向这个新建的点连一条有向边
至于本题的其他部分就没什么好玩的了