DS

第10题
参考洛谷P1025数的划分

#include<iostream>
#include<vector>
using namespace std;

const int N = 300010;
int a[N];
int ans=100000;
vector<int>v;

//x是此次分的，k是剩几次，n是剩下的
void dfs(int x, int k, int n)
{
	if (k == 1)
	{
		v.push_back(n);//把剩下的加进去

		//执行操作
		int temp = 0, index = 0;
		
		//这里出过一次错，这里的k是1，不再是刚开始的1，用v.size()表示分几份
		for (int i = 0; i < v.size(); i++)
		{
			//等于1不计数
			if (v[i] > 1)
			{
				index += v[i];
				temp = temp + a[index - 1] - a[index - v[i]];
			}
		}
		ans = min(ans, temp);
		v.pop_back();// 回溯，移除最后添加的元素,恢复现场
		return;
	}

	for (int i = x; i <= n; i++)
	{
		v.push_back(i);//这次分i
		dfs(i, k - 1, n - i);
		v.pop_back();//动态规划，回溯要恢复现场  
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	dfs(1, k, n);
	cout << ans << endl;
	return 0;
}