欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心

程序员文章站 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; 
}