题解：CF2038L Bridge Renovation

题目链接

题目大意

已知一个木块的长度是60，问你怎么拆可以用最少得木条拆出n个18，n个21，n个25的小木条。

思路

我们很容易发现当最优方案一定是以下3种，其他方法一定比这3种要劣。

方案一：2根21和1根18
方案二：2根25
方案三：3根18

我们能够发现7根长度为60的木条正好可以裁出6根25,6根21和6根18。方案为3次方案一，3次方案二和1次方案三

则对于每6组木板，我们都会使用7根长度为60的木板，且这一定是最优的。

接下来考虑剩下的1~5组模板的数量，模拟可以得到：

裁出1组需要2根
裁出2组需要3根
裁出3组需要4根
裁出4组需要5根
裁出5组需要6根

我们可以把上述结果预处理成一个数组a，则我们输出是只需要输出

\lfloor \frac{n}{6} \rfloor

+ a[n mod 6]。

代码实现

CPP

#include<iostream>
#include<cstdio>

using namespace std;

int n,a[10];

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

int main()
{
	n=read();
	a[1]=2;
	a[2]=3;
	a[3]=4;
	a[4]=5;
	a[5]=6;//预处理剩余1,2,3,4,5根时需要的木条数量 
	cout<<n/6*7+a[n%6];//输出n/6*7+a[n%6],当n=6时，默认+0，不会影响结果 
	return (0^0);
}

完结撒花~~~

~~本人第1篇题解，望通过。~~

题解：CF2038L Bridge Renovation

文章操作

题目大意

思路

代码实现

相关推荐

评论

题解：CF2038L Bridge Renovation