b*7
2 楼
最近提了几个题,大家都特别支持,非常感谢!!
Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
assuming we knew that such a solution must exist.
这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
subproblems.
F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能
有很巧的方法表示这个。请各位大虾赐教啊!
Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
assuming we knew that such a solution must exist.
这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
subproblems.
F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能
有很巧的方法表示这个。请各位大虾赐教啊!
n*3
3 楼
Immunol Rev. 1995 Jun;145:5-31.
Liposomes as carriers of peptide antigens: induction of antibodies and
cytotoxic T lymphocytes to conjugated and unconjugated peptides.
Alving CR, Koulchin V, Glenn GM, Rao M.
please send the paper to e********[email protected]
Liposomes as carriers of peptide antigens: induction of antibodies and
cytotoxic T lymphocytes to conjugated and unconjugated peptides.
Alving CR, Koulchin V, Glenn GM, Rao M.
please send the paper to e********[email protected]
a*y
4 楼
可以
等着修改意见回来了再改也行
等着修改意见回来了再改也行
b*e
5 楼
No solution to this one, you can pretty much give up.
Google:
- Partition problem
- NP hard
- NP completeness
Google:
- Partition problem
- NP hard
- NP completeness
a*l
6 楼
g*y
7 楼
yes, it's NPC
set partition
正号和符号其实就是对数组的一个partition,F等于0,就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP,或者用backtracking的方法做。
1
【在 b******7 的大作中提到】
: 最近提了几个题,大家都特别支持,非常感谢!!
: Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
: or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
: assuming we knew that such a solution must exist.
: 这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
: subproblems.
: F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能
: 有很巧的方法表示这个。请各位大虾赐教啊!
set partition
正号和符号其实就是对数组的一个partition,F等于0,就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP,或者用backtracking的方法做。
1
【在 b******7 的大作中提到】
: 最近提了几个题,大家都特别支持,非常感谢!!
: Given N signed integers A[1,...,N], find N correct signs S[1,..,N] (S[i] = 1
: or -1), such that F[N] = A[1]*S[1] + A[2]*S[2] + ... + A[N}*S[N] = 0,
: assuming we knew that such a solution must exist.
: 这道题我想了很久也不会。感觉上使用DP. 但是找不出比较巧的方法来表示
: subproblems.
: F[N] = 0, 则|F[N-1]| = |S[N]|, 然后每个subproblem A[i] 不过有2个值,应该能
: 有很巧的方法表示这个。请各位大虾赐教啊!
相关阅读
缺少梦想是千老最大的问题Cell子刊审稿这个状态啥意思?一些发考题们的主要问题环境化学,毒理学方面文章求互相引用 (转载)千老数学水平差是硬伤钱学森相信特异功能吗?他用党性保证特异功能是真的!川农教授在Cell发论文,校方奖励1350万。你怎么看?一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程做植物的觉得Plant Direct杂志如何还是叫西葫芦大学比较好美国的科研投入,相当于凯恩斯时期的“以工代赈”2017 部分 impact factor《金融时报》中国发起学术打假行动都转行了谁来研究癌症阿J1豁免苦恼,请教几个生物界的问题?转行的不要来“唤醒”生物学家们了,18岁以上都能自己决定和谁处对象了别人转行成功,自己转行死得很惨转了码工之后苦不堪言的经历跟风说几点转行