結果

問題 No.10 ＋か×か
ユーザー kaffelunkaffelun
提出日時 2018-04-06 01:04:32
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 886 bytes
コンパイル時間 3,459 ms
コンパイル使用メモリ 145,976 KB
実行使用メモリ 7,480 KB
最終ジャッジ日時 2023-09-08 17:55:14
合計ジャッジ時間 8,337 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 WA -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int N;
int Total;
vector<int> A;

const int64_t INF = INT64_MAX;

// k: 深さ
// n: 残りの値
// a: 演算履歴
int64_t dp(int k, int64_t n, int64_t a) {
	// cout <<  k << ":" << n << "_" << a << endl;
	if(k <= 0) {
		if(n != A[0]) {
			return INF;
		} else {
			return a;
		}
	}
	if(n < 0) return INF;
	int64_t retval = dp(k - 1, n - A[k], a);
	// cout << retval << endl;
	if(n % A[k] == 0) {
		retval = min(dp(k - 1, n / A[k], a | (1 << (k - 1))), retval);
	}
	return retval;
}

// 方針:
// 逆向きのDPで攻める。
// X [*|+] A = Total を解いていく。掛け算を削りやすい。

int main() {
	cin >> N >> Total;
	A = vector<int>(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	int64_t ans = dp(N - 1, Total, 0);
	for(int i = 0; i < N - 1; i++) {
		cout << (ans & (1 << i) ? '*' : '+');
	}
	cout << endl;
	return 0;
}
0