首页 > 代码库 > 【四边形不等式】HDU3506-Monkey Party
【四边形不等式】HDU3506-Monkey Party
【题目大意】
香蕉森林里一群猴子(n<=1000)围成一圈开会,会长给他们互相介绍,每个猴子需要时间a[i]。每次只能介绍相邻的两只猴子x和y认识,同时x所有认识的猴子和y所有认识的猴子也就相互认识了,代价为这两伙猴子认识的时间(a[])之和。求这群猴子都互相认识的最短时间。
【思路】
四边形不等式笔记ψ(._. )>
四边形不等式标准转移方程格式:
W(i,j )要满足四边形不等式,当且仅当同时满足:
①j 不变时,f(i) = w(i, j + 1) - w(i, j)单调递减。
②i 不变时,f(j) = w(i + 1, j) - w(i, j)单调递减。
遇到环的问题就把原数组复制一遍,数组长度增加一倍。
dp[i][j]表示从i到j的猴子都是朋友的最小所需时间,sum[i]为前缀。
dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]),其中w[i,j] =sum[j]-sum[i-1]。
显然满足四边形不等式o(* ̄︶ ̄*)o
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=1000+50; 7 const int INF=0x7fffffff; 8 int n; 9 int a[MAXN*2],sum[MAXN*2];10 int dp[MAXN*2][MAXN*2],s[MAXN*2][MAXN*2];11 12 void init()13 {14 for (int i=1;i<=n;i++)15 {16 scanf("%d",&a[i]);17 a[i+n]=a[i];18 }19 sum[0]=0;20 for (int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];21 }22 23 void solve()24 {25 memset(dp,0,sizeof(dp));26 memset(s,0,sizeof(s));27 for (int i=1;i<=2*n;i++) s[i][i]=i;28 for (int i=2*n;i>=1;i--)29 {30 for (int j=i+1;j<=2*n;j++)31 {32 dp[i][j]=INF;33 for (int k=s[i][j-1];k<=s[i+1][j];k++)34 {35 if (dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])36 {37 s[i][j]=k;38 dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];39 }40 }41 }42 }43 int ans=INF;44 for (int i=1;i<=n;i++) ans=min(ans,dp[i][i+n-1]);45 printf("%d\n",ans);46 }47 48 int main()49 {50 while (scanf("%d",&n)!=EOF)51 {52 init();53 solve();54 }55 return 0;56 }
【四边形不等式】HDU3506-Monkey Party
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。