結果

問題 No.10 ＋か×か
ユーザー yuki2006
提出日時 2014-10-11 03:51:56
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,552 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 6,784 KB
実行使用メモリ 9,344 KB
最終ジャッジ日時 2024-12-30 08:33:12
合計ジャッジ時間 5,553 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-

def solve(N, total, A):
    MAX = (1 << N + 2)
    dp = [MAX] * (total + 1)
    # 結果をビットで保存するDP
    dp[A[0]] = 0

    for i, a in enumerate(A[1:]):
        for v in xrange(total, 0, -1):
            if dp[v] == MAX:
                continue

            current = dp[v]
            # 1倍の時に上書きされてしまう対策
            mul_change = False
            if v * a <= total:
                if i == 0:
                    dp[v * a] = (1 << ((N - 2) - i))
                    mul_change = True
                else:
                    if a == 1:
                        mul_change = True
                        dp[v * a] = current | (1 << ((N - 2) - i))
                    else:
                        dp[v * a] = min(dp[v * a], current | (1 << ((N - 2) - i)))

            if v + a <= total:
                if i == 0:
                    dp[v + a] = 0
                else:
                    dp[v + a] = min(dp[v + a], current)

            if not mul_change:
                # 1倍の時以外はMAXにする。
                # 1倍の時にすると値が消えてしまう。
                dp[v] = MAX

    ans_bit = dp[total]
    if ans_bit == MAX:
        return None
    ans = ""

    while N > 1:
        ans = ("*" if ans_bit & 1 else "+") + ans
        ans_bit >>= 1
        N -= 1
    return ans



N = int(raw_input())
total = int(raw_input())
A = map(int, raw_input().split(" "))

print solve(N, total, A)
0