51Nod 2386 分则能成

Problem

牛牛刚开始有一个正整数n。每次操作牛牛可以选择一个自己有的数字x，把x分为两正整数y和z，需满足x=y+z，然后获得y*z的收益。（当然，在这个过程中，牛牛会失去x这个数字，并且获得y和z这2个数字。）

牛牛一共可以分k次，牛牛希望最大化这k次的收益之和。因为分割的结果y和z是正整数，所以选择的x必须>=2。

对于100%的数据，1 <= k < n <= 10^9 对于40%的数据，1 <= k < n <= 10 对于70%的数据，1 <= k < n <= 100

Solution

问题等价于把n拆分成k+1份，然后我们设为a1，a2，...，ak+1，发现最后答案为两两相乘，n^{2=(a1+a2+a3...+ak+1)}2=ans+2sum(ai^2)，求ans最大即为求平方和最小，可以假设2x=c，然后用两个x和(x-1)、(x+1)平方和相减，发现前者始终是最小的，于是转化为接近分组。（具体数学上好像有相关的，不过没带回书也不知道是啥）

Code

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,k;
int main(){
	cin>>n>>k;
	k++;
	int d=n/k;
	ll sum=(k-n%k)*d*d+n%k*(d+1)*(d+1);
	ll ans=(n*n-sum)/2;
	cout<<ans<<endl;
    return 0;
}