結果

問題 No.783 門松計画
ユーザー mai
提出日時 2017-07-19 00:32:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 2,619 bytes
コンパイル時間 3,426 ms
コンパイル使用メモリ 213,788 KB
最終ジャッジ日時 2025-01-05 01:42:26
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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