Tháo dỡ đường ray


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Thành phố quy hoạch lại giao thông đường sắt cần phải tháo dỡ đường ray để chuyển thành đường bộ. Theo đặc thù nên đường ray sẽ được tháo ra thành các đoạn có độ dài theo đúng thứ tự là \(a_1, a_2, ..., a_n\) từ trái sang phải. Chi phí để tháo một đoạn thành 2 bằng đúng độ dài đoạn đó. Thứ tự các đoạn ray tháo ra phải đảm bảo nhưng cách tháo tùy theo bạn. Bạn hãy tư vấn tháo ra sao cho tổng chi phí ít nhất.

Ví dụ: Đường ray dài 24 đơn vị độ dài cần tách ra thành các đoạn độ dài 4, 6, 3 và 11 đơn vị độ dài:

Tháo dỡ từ trái sang phải chi phí:

• 24 tách thành 4 và 20, chi phí 24.

• 20 tách thành 6 và 14, chi phí 20.

• 14 tách thành 3 và 11, chi phí 14.

Tổng chi phí: 58

Một cách khác

• 24 tách thành 13 và 11, chi phí 24.

• 13 tách thành 4 và 9, chi phí 13.

• 9 tách thành 6 và 3, chi phí 9.

Tổng chi phí: 46

Input

Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 100)

Dòng sau chứa n số nguyên dương a1, a2, ..., an, có tổng không vượt quá 10^5

Output:

Một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Ví dụ

Input

4
4 6 3 11

Output

46
tichpx

Comments


  • 0
    TICHPX  commented on Jan. 19, 2019, 9:27 a.m.

    Code tham khảo quy hoạch động

    #include<bits/stdc++.h>
    using namespace std;
    int c[105][105],a[105],b[105];
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            b[i]=b[i-1]+a[i];
        }
        for(int i=2;i<=n;i++)
        for(int j=1;j<=n+1-i;j++)
        {
            c[i][j]=INT_MAX;
            for(int k=1;k<i;k++)
            if(c[i][j]>c[k][j]+c[i-k][j+k]) c[i][j]=c[k][j]+c[i-k][j+k];
            c[i][j]+=b[i+j-1]-b[j-1];
        }
        printf("%d",c[n][1]);
    }