結果

問題 No.783 門松計画
ユーザー maimai
提出日時 2017-07-19 00:32:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 2,619 bytes
コンパイル時間 3,099 ms
コンパイル使用メモリ 212,320 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-30 18:37:48
合計ジャッジ時間 4,754 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 12 ms
4,380 KB
testcase_11 AC 25 ms
4,380 KB
testcase_12 AC 15 ms
4,380 KB
testcase_13 AC 5 ms
4,376 KB
testcase_14 AC 8 ms
4,380 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 5 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 7 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 5 ms
4,376 KB
testcase_25 AC 4 ms
4,376 KB
testcase_26 AC 6 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;

// -----------------------------------------------------------------------
// 
// -----------------------------------------------------------------------


inline bool kadomatu(int a, int b, int c) {
    return (a != c) && ((a<b&&b>c) || (a>b&&b<c));
}


int n, cap;
int price[111], len[111];

// 動的計画法．
// [価格][直前に選んだ竹][さらにその前に選んだ竹]
int dp[51][51][51];


int main() {
    
    // あまり評判の良くない[要出典]std::cinで読み込み
    cin >> n >> cap;
    for (int i=0;i<n;++i) {
        cin >> len[i];
    }
    for (int i=0;i<n;++i) {
        cin >> price[i];
    }

    int result = 0;
    
    // ----------------------------------
    // 最初に購入する竹を列挙，dpにセットする．
    for (int i = 0; i < n; ++i) {
        if (price[i] <= cap)
            dp[price[i]][len[i]][0] = len[i];
    }

    // 個数制約なしナップサック問題と同じ感覚な1順目ループ
    // 既にcost円購入済み，次に何を買うか？
    for (int cost = 0; cost < cap; ++cost) {
        
        // 直前に選んだ竹の組み合わせを全列挙
        for (int pre = 0; pre <= 50; ++pre) {
            for (int prepre = 0; prepre <= 50; ++prepre) {
                
                // 次に選ぶ竹を列挙
                for (int i = 0; i < n; ++i) {
                    
                    // 所持金を超えるのはダメ
                    if (cost + price[i] > cap) continue;
                    
                    // 存在し得ない状態は無視
                    if (dp[cost][pre][prepre] == 0) continue;
                    
                    // 2個未満，あるいは門松列を満たすのであれば
                    if (prepre == 0 || kadomatu(len[i], pre, prepre)) {
                        
                        // 配るDP
                        dp[cost + price[i]][len[i]][pre]
                            = max(
                                dp[cost + price[i]][len[i]][pre],
                                dp[cost][pre][prepre] + len[i]);
                        
                        // 3つ以上の竹を購入したならば，竹の長さの総和の最大値を更新しておく．
                        if (prepre != 0)
                            result = max(result, dp[cost + price[i]][len[i]][pre]);
                    }
                }
            }
        }
    }

    cout << result << endl;


    return 0;
}
0