贪心
程序员文章站
2022-06-13 12:29:27
...
1.什么是贪心
贪心其实是一种思想,即它总是考虑在当前状态下局部最优的策略,来使全局的结果达到最优。如果采取较优而非最优的策略,那么得到的全局结果也无法是最优的,因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法。
2.典例
对于这个问题我们不难发现,其实最终产生价格不同的在于超过8公里的部分,如果超过8公里的部分仍然大于8 ,那么不如将它分成两部分进行计算,这样会比乘以单价要便宜
代码如下:
#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
double id[maxn];//这里的id数组是一个记忆化数组,不然内存超限
double f(int a)
{
double sum1=maxn,sum2=maxn;
if(id[a]!=0)
return id[a];
if(a<=4)
sum1=10;
else if(a>4&&a<=8)
sum1=2*a+2;
else if(a>8)
{
sum1=2.4*a-1.2;
sum2=18+f(a-8);
}
if(sum1<sum2) return id[a]=sum1;
else return id[a]=sum2;
}
int main( )
{
int n;
double ans;
while(~scanf("%d",&n)&&n)
{
ans=f(n);
if(ans-(int)ans!=0)
printf("%.1lf\n",ans);
else
printf("%d\n",(int)ans);
}
return 0;
}
上一篇: flv 文件格式详解
下一篇: 切长条 贪心
推荐阅读