首页 > 代码库 > 【四边形不等式】COGS1658- [HZOI 2014] 合并石子
【四边形不等式】COGS1658- [HZOI 2014] 合并石子
【题目大意】
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得。
【思路】
设 dp[i][j] 表示第 i 到第 j 堆石子合并的最优值，sum[i][j] 表示第 i 到第 j 堆石子的总数量。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int N=205; 5 const int INF=0x7fffffff; 6 int n; 7 int a[N],sum[N],dp[N][N],s[N][N]; 8 9 void f()10 {13 for (int i=1;i<=n;i++) dp[i][i]=0,s[i][i]=i;14 for (int r=1;r<n;r++)15 {16 for (int i=1;i<n;i++)17 {18 int j=i+r;19 if(j>n) break;20 dp[i][j]=INF;21 for (int k=s[i][j-1];k<=s[i+1][j];k++)22 {23 if(dp[i][j]>dp[i][k]+dp[k+1][j])24 {25 dp[i][j]=dp[i][k]+dp[k+1][j];26 s[i][j]=k;27 }28 }29 dp[i][j]+=sum[j]-sum[i-1];30 }31 }32 }33 34 int main()35 {36 while(~scanf("%d",&n))37 {38 sum[0]=0;39 for (int i=1;i<=n;i++)40 {41 scanf("%d",&a[i]);42 sum[i]=sum[i-1]+a[i];43 }44 f();45 printf("%d\n",dp[1][n]);46 }47 return 0;48 49 }
【四边形不等式】COGS1658- [HZOI 2014] 合并石子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。