首页 > 代码库 > 【cogs858】磁性链

【cogs858】磁性链

2024-07-03 21:39:26   225人阅读

【题目描述】

有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}

 

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 const int maxn=1005;
 7 const int maxq=105;
 8 const int INF=1000*1000;
 9 using namespace std;
10 int f[maxn][maxn],shu[maxq];
11 int main()
12 {
13     int i,j,n,m;
14     //文件操作
15     memset(shu,0,sizeof(shu));
16     memset(f,0,sizeof(f));
17     
18     scanf("%d%d",&m,&n);
19     for (i=1;i<=n;i++) scanf("%d",&shu[i]);
20     sort(shu+1,shu+1+n);
21     shu[n+1]=m+1;
22     
23     for (i=1;i<=n;i++) f[i][i]=shu[i+1]-shu[i-1]-2;
24     for (m=1;m<=n;m++)
25     for (i=1;i<=n-m+1;i++)
26     {
27         int j=i+m; 
28         f[i][j]=INF;
29         for (int k=i;k<=j;k++) 
30         f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+shu[j+1]-shu[i-1]-2);
31     }
32     printf("%d",f[1][n]);
33     return 0;
34 }
View Code

 

 

 

 

 


联系
我们