牛客入门题单dp篇--1003可爱の星空

题目链接：1003-可爱の星空_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)

 思路：想想可知两堆之间的数量差距越小越好，所以最后一次合并一定是n/2，n/2(偶数)或n/2，n/2+1(奇数)，以此类推这两堆再对半分，知道有一堆为1或2时显而易见合并花费为0，开始回溯。

偶数的合并solve(n/2)+solve(n/2)

奇数的合并必有n/2+1-n/2=1的花费所以奇数堆的合并是solve(n/2)+solve(n/2+1)+1

写的小草稿：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll ans = 0;
map < ll, ll > mp;  //n很大，为了避免重复计算要记忆化搜索

ll solve(ll int n) {
	if (n == 2 || n == 1) {
		mp[n] = 0;
		return 0;
	}
	if (mp.find(n)!=mp.end()) {  //用find函数可以避免多余的零二元组
		return mp[n];
	}
	if (n % 2 == 0) {
		mp[n / 2] = solve(n / 2);
		ans = mp[n / 2] * 2;
	}
	else {
		mp[n / 2] = solve(n / 2);
		mp[n / 2 + 1] = solve(n / 2 + 1);
		ans = mp[n / 2] + mp[n / 2 + 1] + 1;
	}
	return ans;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		ll int n;
		cin >> n;
		cout << solve(n) << endl;
	}

	return 0;
}