|
题意:给出在同一条直线上的n个点和两个数A,B,现在要在这条直线上放置若干个信号塔,每个信号塔有一个r值,假设它的位置是x,则它能覆盖的范围是x-r~x+r,放置一个信号塔的花费是A+B*r,问要覆盖所有的点最小的花费是多少。
分析:看了飞鸿哥的报告才明白的,DP神马的弱爆了=_=
dp表示从点1到i最多放置i个信号塔的最小花费。先预处理[1,i]区间放置一个信号塔的花费,然后枚举最多放置2~n个信号塔求最小花费,最后dp[n]就是答案了。
状态转移方程:dp=min(dp,dp[j]+a+(num-num[j+1])*b/2.0)
这题的输出有点麻烦,有整数也有浮点数,所以要判断一下在输出。
AC代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 using namespace std;
5 double dp[2005];
6 int num[2005];
7 double min(double a,double b)
8 {
9 return a<b?a:b;
10 }
11 int main()
12 {
13 int n,a,b,i,j;
14 scanf("%d%d%d",&n,&a,&b);
15 for(i=1;i<=n;i++)
16 scanf("%d",&num);
17 sort(num+1,num+1+n);
18 for(i=1;i<=n;i++)
19 dp=a+(num-num[1])/2.0*b;
20 for(i=2;i<=n;i++)
21 for(j=1;j<i;j++)
22 dp=min(dp,a+(num-num[j+1])/2.0*b+dp[j]);
23 int ans=dp[n];
24 if(dp[n]>ans)
25 printf("%d.5\n",ans);
26 else
27 printf("%d\n",ans);
28 return 0;
29 }
View Code |
|
|