欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDOJ3506 Monkey Party #区间DP 四边形不等式#

程序员文章站 2022-06-19 13:30:27
...

Monkey Party

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4755    Accepted Submission(s): 1738

Problem Description
 
Far away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate Crazy Bananas Day. But the little monkeys don't know each other, so as the king, SDH must do something.
Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are:
1.every time, he can only introduce one monkey and one of this monkey's neighbor.
2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows;
3.each little monkey knows himself;
In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing.
 
Input
 
There is several test cases. In each case, the first line is n(1 ≤ n ≤ 1000), which is the number of monkeys. The next line contains n positive integers(less than 1000), means the making friends time(in order, the first one and the last one are neighbors). The input is end of file.
 
Output
 
For each case, you should print a line giving the mininal time SDH needs on introducing.
 
Sample Input
 
8 5 2 4 7 6 1 3 9
 
Sample Output
 
105
 
Author
 
PerfectCai
 
Source
 
 
Recommend
 
zhengfeng
 

Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e3 + 10;
int n, psum[maxn << 1], pos[maxn << 1][maxn << 1], dp[maxn << 1][maxn << 1];

inline const int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); }
    return x * f;
}

int getSum(int a, int b) { return psum[b] - psum[a - 1]; }

int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 1; i < n << 1; i++)
        {
            if (i <= n) psum[i] = psum[i - 1] + read();
            else psum[i] = psum[n] + psum[i - n];
            pos[i][i] = i;
            dp[i][i] = 0;
        }
        int res = 0x3f3f3f3f;
        for (int len = 1; len < n; len++)
        {
            for (int i = 1, j = i + len; j < n << 1; i++, j++)
            {
                dp[i][j] = 0x3f3f3f3f;
                for (int k = pos[i][j - 1]; k <= pos[i + 1][j]; k++)
                {
                    if (dp[i][j] > dp[i][k] + dp[k + 1][j] + getSum(i, j))
                    {
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + getSum(i, j);
                        pos[i][j] = k;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) res = min(res, dp[i][i + n - 1]);
        printf("%d\n", res);
    }
    return 0;
}

 

相关标签: Online Judge