首页 > ACM题库 > HDU-杭电 > HDU 3506-Monkey Party-动态规划-[解题报告]HOJ
2014
04-09

HDU 3506-Monkey Party-动态规划-[解题报告]HOJ

Monkey Party

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

8
5 2 4 7 6 1 3 9

样例输出:

105

题目类型:动态规划,属于区间性质的,可以利用四边形不等式加速。

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3506

题目大意:一群猴子围成圈,每个猴子互相不认识,猴王要给大家互相认识,每个猴子认识别人需要一个时间花费,而且A猴子认识B猴子,则A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这个代价为所有AB猴子认识的猴子的时间花费和。   说的很绕,可以读下题,题目意思就是这样的。

思路:运用动态规划,枚举每个区间的分割点,从而找到最小花费。因为题目中给出的是环,解决的方法就是设一个长度为2*n的数组可以将环转化为线性。

转移方程:dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[i][j]    i<k<j)

代码:

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

using namespace std;

const int maxx=2002;

int dp[maxx][maxx],mark[maxx][maxx],sum[maxx][maxx];
//dp[i][j]表示第i个猴子到第j个猴子认识的总代价
//mark[i][j]标示最小分割点处的k值  用于四边形加速
//sum[i][j]i到j花费总和
int data[maxx];

int min(int a,int b){
    return a<b?a:b;
}

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&data[i]);
            data[i+n]=data[i];
        }
        memset(sum,0,sizeof(sum));
        for (int i=1;i<2*n;i++)
        {
            dp[i][i]=0;
            mark[i][i]=i;
            for (int j=i;j<=n+i;j++)
            {
                sum[i][j]=sum[i][j-1]+data[j];
            }
        }
        for (int st=2;st<=n;st++)
        {
            for (int i=1;i+st<=2*n+1;i++)
            {
                int j=i+st-1;
                dp[i][j]=99999999;
                for (int k=mark[i][j-1];k<=mark[i+1][j];k++)
                {
                    int temp=dp[i][k]+dp[k+1][j]+sum[i][j];
                    if (dp[i][j]>temp)
                    {
                        dp[i][j]=temp;
                        mark[i][j]=k;
                    }
                }
            }
        }
        int ans=9999999;
        for (int i=1;i<=n;i++)
        {
            ans=min(ans,dp[i][i+n-1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/iaccepted/article/details/6823198


  1. 顶一个,这个原理我也很早就知道。这篇文章的出处尚未经过考证。不是说给一个英文的链接它就是真实的,网上随便哪个外国人谁写个文章,我们转载过来都是这样的,因此写这篇文章的人不知是何居心呢

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  4. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……