結果

問題 No.10 ＋か×か
コンテスト
ユーザー kaffelun
提出日時 2018-04-06 01:04:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 886 bytes
コンパイル時間 1,444 ms
コンパイル使用メモリ 160,352 KB
実行使用メモリ 14,008 KB
最終ジャッジ日時 2024-06-26 10:42:04
合計ジャッジ時間 8,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 1 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

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