1つのコマが、生涯(そのコマから派生した全てのコマがなくなるまで)で
何回分の操作に相当するか、というのは、そのコマがどこに置かれているかで一意に決まる。
⑥←⑨→③→①
↓ ↓ ↓ W_i が 大→小 の方向にしかコマは流れないので、
③←④→② 辺は有効辺と見なす
↓
①
上記の①や②など、流出辺(自分より Wi が小さい隣接頂点)がなければ、
そのコマを取り除いた後は新たなコマを置けないので、可能な操作は1回のみ。
⑨や④など流出辺がある場合は、「和が自身の Wi を超えないように、隣接頂点から、1個あたりの操作回数が大きいものを選ぶ」ことになる。
これは、まさしくナップサック問題で、
ナップサックの容量を Wi、各隣接頂点 j につき Wj を重さ、DP[j] を価値とした問題を解けばよい。
Wi の小さい方からDPを埋めていけば、Wi を求めるときには、必要な DP[j] は埋まっている。
1回当たり m 個の荷物で容量 w のナップサック問題を解くとして、O(mw)、
これを各頂点に対して合計して、O(MWmax) となる。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
n, m = map ( int , input ().split())
links = [ set () for _ in range (n)]
for _ in range (m):
u, v = map ( int , input ().split())
u - = 1
v - = 1
links[u].add(v)
links[v].add(u)
www = list ( map ( int , input ().split()))
aaa = list ( map ( int , input ().split()))
bbb = [(w, i) for i, w in enumerate (www)]
bbb.sort()
value = [ 1 ] * n
ans = 0
for wu, u in bbb:
dp = [ 0 ] * wu
for v in links[u]:
wv = www[v]
if wu < = wv:
continue
vv = value[v]
for i in range (wu - wv - 1 , - 1 , - 1 ):
dp[i + wv] = max (dp[i + wv], dp[i] + vv)
value[u] = max (dp) + 1
ans + = aaa[u] * value[u]
print (ans)
|
区間の平均は、割る数が長さによって異なってくるため、[l,r) の時の結果を [l−1,r) や [l,r+1) に活用しづらい。
平均が、「累積和の傾き」によって表現できることを利用する。
14 | * A = ( 1, 1, 4, 5, 3)
|
| 累積和C = (0, 1, 2, 6,11,14)
11 | *
|
|
|
|
6 | *
|
|
|
2 | *
1 | *
+---------------
1 2 3 4 5
傾きで考えると、上側凸包に含まれない点を考える必要がなくなる。
| *
| ,-'
| ,-'
| ,-' * ← j は i より左の点を l とした時の r にはなり得ない
| *' 必ず i か k を r とした方が傾きが大きくなる
=
|
+-||----------------
i j k
i の大きい方から凸包を構成していけば、O(N) で求まる。
Python3
上記の理論と、凸包の構成の仕方さえ分かれば、実装はとても簡単。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
from itertools import accumulate
n = int ( input ())
aaa = list ( map ( int , input ().split()))
acc = [ 0 ] + list (accumulate(aaa))
ans = [ 0 ] * n
stack = [n]
for i in range (n - 1 , - 1 , - 1 ):
a = acc[i]
while len (stack) > = 2 :
j = stack[ - 1 ]
k = stack[ - 2 ]
b = acc[j]
c = acc[k]
ave1 = (b - a) / (j - i)
ave2 = (c - a) / (k - i)
if ave1 < = ave2:
stack.pop()
else :
break
j = stack[ - 1 ]
b = acc[j]
ave = (b - a) / (j - i)
ans[i] = ave
stack.append(i)
print ( '\n' .join( map ( str , ans)))
|