結果

問題 No.107 モンスター
ユーザー syoken_desukasyoken_desuka
提出日時 2015-07-11 17:15:07
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 20 ms / 5,000 ms
コード長 3,102 bytes
コンパイル時間 698 ms
コンパイル使用メモリ 91,324 KB
実行使用メモリ 7,596 KB
最終ジャッジ日時 2023-08-22 22:58:42
合計ジャッジ時間 1,983 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,456 KB
testcase_01 AC 4 ms
7,428 KB
testcase_02 AC 5 ms
7,496 KB
testcase_03 AC 4 ms
7,464 KB
testcase_04 AC 4 ms
7,436 KB
testcase_05 AC 4 ms
7,492 KB
testcase_06 AC 4 ms
7,492 KB
testcase_07 AC 4 ms
7,540 KB
testcase_08 AC 4 ms
7,492 KB
testcase_09 AC 4 ms
7,424 KB
testcase_10 AC 4 ms
7,488 KB
testcase_11 AC 5 ms
7,496 KB
testcase_12 AC 5 ms
7,596 KB
testcase_13 AC 6 ms
7,540 KB
testcase_14 AC 12 ms
7,568 KB
testcase_15 AC 12 ms
7,488 KB
testcase_16 AC 4 ms
7,556 KB
testcase_17 AC 5 ms
7,492 KB
testcase_18 AC 17 ms
7,464 KB
testcase_19 AC 17 ms
7,580 KB
testcase_20 AC 8 ms
7,596 KB
testcase_21 AC 7 ms
7,540 KB
testcase_22 AC 9 ms
7,420 KB
testcase_23 AC 20 ms
7,488 KB
testcase_24 AC 15 ms
7,464 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:81:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
 #endif _DEBUG
        ^~~~~~
main.cpp:93:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
 #endif _DEBUG
        ^~~~~~
main.cpp:104:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
 #endif _DEBUG
        ^~~~~~

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <ostream>
#include<complex>
#include <cmath>
#include <iostream>
#include <stack>
#include <fstream>
#include <queue>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <string>
using namespace std;
#define OB (bitset<32>)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define ALLOF(c) begin(), (c),end()
typedef long long ll;


//BitUtility
#define B_VOID 0
#define B_ONLY_I(i) (1<<i)
#define B_ALL_SIZE_K(k) ((1<< k)-1)
#define B_S_CONTAIN_I(S,i) (S >> i & 1)
#define B_ADD_I(S,i) (S | 1 << i)
#define B_REMOVE_I(S,i) (S & ~(1 << k))
#define B_JOIN(A,B) (A | B)
#define B_SET_A_SUB_B(A,B) (B_JOIN(A,B) & ~B)
#define B_INTERSECTION(A,B) (S & T)
#define B_BOTTOM_BIT(i) (i & -i)
/*snippet list
bitpermutation
*/

int main()
{ 
    int n;
    int d[16];
    int dp[1 << 16][16];//のこった体力 倒した敵、その時のレベル　
    int max_level = 0;
    int end_code;
    cin >> n;
    fill(d,d+16,1000000);// 1000より大きく
    rep(i,n)
        cin >> d[i];
    sort(d, d + 16);
    end_code = 1 << n - 1;
    fill(*dp, *dp  + ((1<<16) * 16), 0);

    rep(i,n)
    {
        if (d[i] < 0)
        {
            max_level++;
        }
        else break;
    }
    dp[0][0] = 100; //init HP
    //要素数1,2,...,nのビット集合を昇順に列挙
    //int k = 4;//列挙子の最大個数
    REP(i,1,n+1)
    {
        int comb = (1 << i) - 1;
        while (comb < (1 << n))
        {
            int mask = 1;
#ifdef _DEBUG
            cout <<  OB comb << endl;
#endif _DEBUG      
            //enum before
            for (int j = 0; j < n; j++)
            {
               int before = ~(1 << j) & comb;
               int next = comb;
               if (before == comb)
               { 
                   continue;
               }
#ifdef _DEBUG
               cout << OB before << " to " << OB comb << endl;
#endif _DEBUG   
               int level = 0;
               rep(k,n) // level check
               {
                   if (d[k] < 0)
                   {
                       if (B_S_CONTAIN_I(before,k) != 0)  level++;
                   }else break;
               }
#ifdef _DEBUG
               cout << "now level is " << level << endl;
#endif _DEBUG      
               //hirou dp
               if (d[j] < 0) //teki
               {
                   dp[next][level+1] = max(dp[next][level+1],dp[before][level] + d[j]);//よりよければ更新
               }else // iiyatu
               {
                   if (dp[before][level] == 0) continue; //すでに死んでる
                   dp[next][level] = min(100*(level+1),max(dp[next][level],dp[before][level]+d[j]));
               }
            }
            int x = comb & -comb, y = comb + x;
            comb = (comb & ~y) / x >> 1 | y;
        }
    }
    cout << dp[(1 << n)-1][max_level] << endl;
    return 0;

}
0