4
25
2015
2

2015/04 NEUQ月赛

A.枚举一下倍数就好了

B.经典问题。实际上问的应该是最坏情况下最少需要称多少次。递归一下ok。

C.约瑟夫。。。

D.最短路。。。

E.又被DP卡住了。

  感觉是必须记录和的具体差值的。因为只有最值无法保证子问题最优的性质。

  当然如果既记录具体差值,又记录交换了多少次的话不仅MLE而且TLE。

  然后我就弃疗了,觉得一定是防AK神题!

  然后学姐发了题解,顿时感觉好巧妙啊。

  我们只记录上面的和。用f[i][j]表示前i个数组成和为j最少需要交换多少次,这个满足子问题最优的性质,而且可以很简单的DP。

  太神了,Orz!

  这次是败在了状态的设计上,以后要多下功夫。(好像脑袋里闪过这个思路?但立马被否决了?)

因为E比较好,所以搬运一下题面:

陈船长和xzx每人都有N个玩具,序号从1到N。不同的玩具可能并不一样好玩。
其中陈船长的第i个玩具的好玩度为C[i],xzx的第i个玩具的好玩度为X[i], 好玩度可以是负数,可以理
 
解为不好玩的程度。
你可以交换陈船长的第i个玩具和xzx的第i个玩具,为了让他们两个玩的尽可能一样高兴,他们希望经过
 
不大于K次交换后陈船长所有玩具的好玩度总和与xzx的总和之差的绝对值最小,即 |Sum(C) - Sum(X)| 
 
最小。现在,请你告诉他俩最小值是多少。
多组测试数据,第一行一个整数T(T < 20), 表示测试数据组数。
每组数据第一行两个整数N(0 < N < 100), K(0 < K <= N)。
接下来一行N个整数,第i个数代表C[i](-100 <= C[i] <= 100)。
再接下来一行N个整数, 第i个数代表X[i](-100 <= X[i] <= 100)。
数组下标从0开始。

比赛地址

Category: NEUQ月赛 | Tags: | Read Count: 562
Avatar_small
Tunix 说:
2015年5月11日 14:15

那么神犇您还打5-24的NEUQ吗?老司机带带我?

Avatar_small
Tunix 说:
2015年5月11日 14:21

QAQ脑抽了,怎么删除评论!!那个是现场赛0.0快删评论……


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com