結果

問題 No.783 門松計画
コンテスト
ユーザー 梧桐
提出日時 2026-02-22 15:26:23
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,420 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 966 ms
コンパイル使用メモリ 79,680 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-22 15:26:26
合計ジャッジ時間 1,896 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 60;

// f[u][a][b]: 已用预算为 u 元时，最后两根竹子为第 a 种和第 b 种，序列最大长度总和
int n, c, l[N], w[N], f[N][N][N], ans;

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; ++i) scanf("%d", &l[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

    // 初始化：枚举所有长度不同的两根竹子作为序列开头
    memset(f, 0xcf, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (l[i] != l[j] && w[i] + w[j] <= c) {
                f[w[i] + w[j]][i][j] = l[i] + l[j];
            }
        }
    }
    
    // 转移：尝试在序列末尾追加第 k 种竹子，要求与前两根构成凹凸三元组
    for (int u = 0; u <= c; ++u) {
        for (int a = 1; a <= n; ++a) {
            for (int b = 1; b <= n; ++b) {
                if (f[u][a][b] < 0) continue;
                ans = max(ans, f[u][a][b]);
                for (int k = 1; k <= n; ++k) {
                    if (u + w[k] > c || l[k] == l[a] || l[k] == l[b]) continue;
                    if ((l[a] - l[b]) * (l[k] - l[b]) <= 0) continue;
                    f[u + w[k]][b][k] = max(f[u + w[k]][b][k], f[u][a][b] + l[k]);
                }
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}
0