#include #include // N // Total // A1 A2 … AN // 1行目に、計算式中の整数の数を表すN (2≤N≤50)が与えられる。 // 2行目に、計算式の演算結果を表すTotal (1≤Total≤100,000)が与えられる。 // 3行目に 計算式中の整数を表すAi (1≤Ai≤10) がスペース区切りでN個与えられる。 // +と*しかなくて(つまり、増加のみ)、Totalが最大100000なので、演算結果自体も100000超えはありえないとみなして良いのではないだろうか・・・。 using namespace std; #define REP(i,n) for(int i=0;i::iterator ITR; typedef unsigned long long ULONGLONG; static const ULONGLONG INF=1ULL<<63; int main(void) { int nIntCount = 0; long nTotal = 0; vector vInt; cin >> nIntCount; cin >> nTotal; int nInput = 0; REP(i,nIntCount) { cin >> nInput; vInt.push_back(nInput); } // cout << nIntCount << endl; // cout << nTotal << endl; // REP(nIntCount) cout << vInt[i] << endl; // 計算結果の配列 // この値は、64bit整数だが、イメージ的には、各1bitがフラグとなって加算か乗算かを表現しているイメージ? // ただし、乗算は+1して1桁上まで行かせる vector vRes(nTotal+1, INF); vRes[vInt[0]] = 0; for(int i=1;i vResに保存&今回計算されていない余計なのは消える // (※要は、2回目のループで、下記情報はあってはいけない) // vRes[2]==0 // // 多分、2回目のループでは、vRes[5],vRes[6]のみになっていなければならない vector vResTmp(nTotal+1, INF); REP(j,nTotal+1) { // 各項毎に、可能性のある数値を更新 // この条件より、前に通った値として保存されているもの以外、計算しないことになる? if( vRes[j] == INF ) continue; // jが途中で通る値の1つである // それに現在値を加算または乗算したところに値としてこれまでの演算子パターンを設定 if( j + vInt[i] <= nTotal ) // 値が小さい方が+ 大きい方が*と思われる この問題の場合は+優先 // 該当のビットを立てる(だんだん桁が上がるはず) vResTmp[j + vInt[i]] = min( vResTmp[j + vInt[i]], vRes[j] << 1 ); if( j * vInt[i] <= nTotal ) // 該当のビットを立ててから+1(だんだん桁が上がるはず) // *の場合 +1は、後で+か*かを見分けるのに使用 vResTmp[j * vInt[i]] = min( vResTmp[j * vInt[i]], (vRes[j] << 1) + 1 );//| (1<>(nIntCount-i-2); //if( (tmp & 0x1 ) == 1 ) if( tmp % 2 == 1 ) { cout << '*'; } else { cout << '+'; } } cout << endl; return 0; }