【cogs858】磁性链

时间：2022-11-22 06:03:26

【题目描述】

有N块编号为1~N的特殊磁石相互吸附组成一条磁性链，只有它们紧挨着时才会传递吸力，他们之间的吸力很大，如果我们要从N块相连的磁石中取出一块，那么需要消耗N-1个单位的能量，空缺处不再有吸力传递，空出的位置也不会再被吸到一起。现在我们要取出Q块磁石，并且给出它们的编号，问最少要消耗多少单位的能量？

【输入格式】

第一行两个数N和Q，Q表示要取走的磁石数；

第二行Q个数，表示要取走哪些编号的磁石。

【输出格式】

仅一行，表示最少消耗的能量。

【分析】

一道典型的DP问题，用f(i,j)来表示从i个磁石到第j个磁石所能得到的最小能量和。

用shu[j]-shu[i]-2来表示，从i到j磁石间的距离(当然，你需要排序)。

这样，很容易得到递推方程：

f(i,j)=min{f(i,j),f(i,k-1)+f(k+1,j)+shu[j+1]-shu[i-1]-2}

 #include <cstdlib>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 const int maxn=;

 const int maxq=;

 const int INF=*;

 using namespace std;

 int f[maxn][maxn],shu[maxq];

 int main()

 {

     int i,j,n,m;

     //文件操作

     memset(shu,,sizeof(shu));

     memset(f,,sizeof(f));

     scanf("%d%d",&m,&n);

     for (i=;i<=n;i++) scanf("%d",&shu[i]);

     sort(shu+,shu++n);

     shu[n+]=m+;

     for (i=;i<=n;i++) f[i][i]=shu[i+]-shu[i-]-;

     for (m=;m<=n;m++)

     for (i=;i<=n-m+;i++)

     {

         int j=i+m;

         f[i][j]=INF;

         for (int k=i;k<=j;k++)

         f[i][j]=min(f[i][j],f[i][k-]+f[k+][j]+shu[j+]-shu[i-]-);

     }

     printf("%d",f[][n]);

     return ;

 }

相关文章