【HDU 5772】String problem

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5772
神犇题解:http://www.cnblogs.com/qscqesze/p/5715939.html

解题报告

日常看错题系列:

  1. 子序列看成子串
  2. 值域范围$0 \sim 9$看漏

于是只会跑$n$遍网络流的算法了 QwQ
大概就是枚举左端点,然后暴力跑

考虑原题的话,唯一的Trick就是如何处理一个数第一次选的代价不同
我们可以使用最大权闭合子图来解决这个问题:

每一类数字新建一个结点,权值为$b_i – a_i$
值为该数字的所有序列上的点向这个新建的点连一条有向边

至于本题的其他部分就没什么好玩的了