小进是一个热爱作曲、不善于编程的孩子。一天,他又想编一首有 m 个音符、有 n 种不同音高的曲子。为了方便,将这 n 种音高命名为 1,2,3,4,...,n 。
小进想要让他的音乐尽可能好听,但又不会求解,于是找到了会编程的你。
小进将会告诉你 k 种不同的由 2 个音符组成的旋律,还有这两个音符按某个顺序搭配后,乐曲的美妙度会增加相应的数。
还有一些由两个音符组成的旋律,小进没有给出,也就是这个旋律并不会增加美妙度,也不会减少。
你需要设计一个程序,输出所有可能中最高的美妙度,但是音符数量必须是 m ,且为了避免重复单独,每一个 2 个音符的旋律在这首乐曲中的数量是有限制的。
第 1 行输入 3 个数,分别是 n,m,k 。意义在上面已经给出。
接下来一共 k 行,每一行 4 个数,其中第 i 行的 4 个数分别为 bi,ai,vi,ti ,它们表示第 i 个由 2 个音符组成的旋律是第 ai 个音高的音符在第 bi 个音高的音符后面,这样的旋律的美妙度为 vi ,但在这首歌中只能出现 ti 次。
没有输入的旋律可以出现无数次。
输出 1 个数,即曲子美妙度的最大值。
输入 # 1
9 9 9
6 5 10 1
5 3 8 1
3 5 6 1
5 2 9 1
2 1 8 1
4 7 -1 5
1 2 3 1
2 3 2 1
3 7 1 2
输出 # 1
47
6 5 3 5 2 1 2 3 7
或 6 5 2 1 2 3 5 3 7
1≤n≤88
1≤m≤1500
0≤k≤7656
蒟蒻目前就想到 O(n3m2) (还有问题)的做法,要运算 1,533,312,000,000 次,要约 1500S(25min) 才能运行完。可以注意到这题 O(n3m) 能过,求方法。
O(n3m2) 代码还有缺陷,比如输入
4 7 4
1 4 2 2
4 3 2 2
3 1 2 2
1 2 3 1
时它会在上一个音符是 1 时选用 1 2
。这样会避开正确答案。也求dalao指导优化。如果把每一种情况存进去,最差会使时空复杂度都乘上一个 k 。所以实际上现在还是只有 O(n3m2k)=O(n5m2) 算法。即使您只会优化到真正的 O(n3m2) 水平,也请您留下讲解,谢谢!