题解

本来想用贪心的，但发现大弹射过后还有小弹射，所以只能上动态规划了

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int dp[200005];
int main(){
	//memset(dp, 63, sizeof(dp));
	dp[0] = 0;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		dp[i] = dp[i - 1] + 1;
		for(int j = 1; j * j <= i; j++){
			dp[i] = min(dp[i], dp[i - j * j] + j + 1);
		}
	}
	cout << dp[n - 1];

	return 0;
}