1 条题解

  • 0
    @ 2025-4-9 13:29:05
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 2000;
    const int INF = 2000 * 1'000'000;
    int n;
    int t[MAXN + 5];
    int dp[MAXN + 5][MAXN + 5];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> t[i];
        for (int len = 1; len <= n; len++)
        {
            for (int l = 1; l + len - 1 <= n; l++)
            {
                int r = l + len - 1;
                // 考虑在 k 的位置挖一铲子
                dp[l][r] = INF;
                for (int k = l; k <= r; k++)
                {
                    dp[l][r] = min(dp[l][r],
                                   t[k] + max(dp[l][k - 1], dp[k + 1][r]));
                }
            }
        }
        cout << dp[1][n];
        return 0;
    }
    
    • 1

    信息

    ID
    13405
    时间
    3600ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    9
    已通过
    7
    上传者