1 条题解

  • 1
    @ 2026-9-5 19:36:46
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    const int MAXN = 505;
    const ll INF = 1e18;
    ll dp[MAXN][MAXN];
    
    int main()
    {
        int n;
        cin >> n;
        // len=2,两点,代价0
        for(int i = 1; i <= n; ++i)
            dp[i][i+1] = 0;
    
        // len:区间点的数量,从3到n
        for(int len = 3; len <= n; ++len)
        {
            for(int i = 1; i + len - 1 <= n; ++i)
            {
                int j = i + len - 1;
                dp[i][j] = INF;
                // 枚举分割点k
                for(int k = i+1; k < j; ++k)
                {
                    ll val = dp[i][k] + dp[k][j] + 1LL * i * k * j;
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }
        cout << dp[1][n] << endl;
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    1885
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    147
    已通过
    55
    上传者