Project Euler 122 Efficient exponentiation

开启传送门

题目描述

The most naive way of computing $n^{15}$ requires fourteen multiplications:

$n \times n \times \dots \times n = n^{15}$

But using a “binary” method you can compute it in six multiplications:

\begin{eqnarray}
n \times n &= n^2\\
n^2 \times n^2 &= n^4\\
n^4 \times n^4 &= n^8\\
n^8 \times n^4 &= n^{12}\\
n^{12} \times n^2 &= n^{14}\\
n^{14} \times n &= n^{15}\\
\end{eqnarray}

However it is yet possible to compute it in only five multiplications:

\begin{eqnarray}
n \times n &= n^2\\
n^2 \times n &= n^3\\
n^3 \times n^3 &= n^6\\
n^6 \times n^6 &= n^{12}\\
n^{12} \times n^3 &= n^{15}\\
\end{eqnarray}

We shall define $m(k)$ to be the minimum number of multiplications to compute $n^k$; for example $m(15) = 5$.

For $1 \leq k \leq 200$, find $\sum m(k)$.

题意

我们知道快速计算一个数的幂次有各种不同的方法,快速幂只是其中一种而且不是最快的,然后问你对于1~200的幂次来说,最少需要几次乘法操作.

分析

有一个wiki讲的就是这个问题,可以看一看….

我们可以发现,对于所有幂次来说,我们按照最后一步操作的数来构成他的前驱,然后我们会发现他是一棵树,然后我们直接构造出这颗树出来,就是最优答案…..

代码

给大佬递上我奇丑无比的代码　(/ω＼)

#include<bits/stdc++.h>
using namespace std;
set<int> s[222];
void cal(int a){
	int now = 1e8,ind = 0;
	for(int i = 1;i<=a;i++){//枚举每一个比他小的数,看是否可以作为他的前驱
		if(s[i].size()+1>=now) continue;//如果不能优化解就不继续搜索
		for(int x:s[i])//枚举每一个前驱的子元素
			if(s[i].find(a-x)!=s[i].end()){//如果能构成a
				now = s[i].size()+1;//更新解
				ind = i;
				break;
			}
	}
	for(int i:s[ind]) s[a].insert(i);//保存路径
	s[a].insert(a);
}
int main(){
	s[1].insert(1);
	for(int i = 2;i<=200;i++) cal(i);
	int ans = 0;
	for(int i = 1;i<=200;i++) ans+=s[i].size()-1;//要把里面的1剪掉,因为合成1不要代价
	cout<<ans<<endl;
	return 0;
}