UOJ Logo Alextokc的博客

博客

均分纸牌升级版

2017-07-16 06:49:32 By Alextokc

原题链接: https://www.luogu.org/problem/show?pid=1031

仅将原题题面中的"移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。",改为:"移牌规则为:可以将任意的纸牌个数移到任意编号的堆上"。

对于改动后的问题,存不存在时间复杂度在多项式以内的解法?

评论

WrongAnswer
感觉有点像BZOJ2064……不会多项式时间的解法……
Alextokc
@shanquan2
BillXu2000
这是一个nph问题, 以如下方法构造: 设共有n+2堆 堆1上放x张牌(x>0). 堆2上放y张牌(y>0). 剩下n堆任意放置使得牌数均为负数, 且这n+2堆牌数之和为0. 显然地, 此时答案至少为n, 且判断是否为n需要抉择后n堆中的牌来自堆1还是堆2, 这是背包问题. 故此问题为nph.

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。