欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1462 D. Add to Neighbour and Remove

程序员文章站 2022-05-21 08:13:15
...

https://codeforces.com/contest/1462/problem/D

题意:给你一个数组,对于每个元素可以和左边或右边的元素合并,合并之后成为新的元素,值为合并前的两元素和,求最少经过几次能使数组中剩下的各个元素值相同。

一开始想不出思路,就知道最差情况是操作n-1次把所有元素合并了…后来想了想发现问题可以转化为可以把数组分为几段,每段中的元素和相同,能分的组越多,操作的次数就越少,最终的操作次数就是数组中元素个数-段落数(很容易推出来),所以就去求最多能分成几段。
然后可以发现线段中元素和的情况分成a[1],a[1]+a[2],a[1]+a[2]+a[3],…,a[1]+a[2]…+a[n],对于每一种情况的值记为sum,然后dfs,每次dfs设count=1,ans=0,每次ans+=a[i],如果ans=sum,count+1。但是这样还不够,因为例如 2 2 1的情况下这样算就会算出操作1次,实际上是2次,所以我们要判断ans=sum时i是否等于n(i=n同时ans=sum说明圆满完成分段~),是的话就触发条件,count能够更新。

要注意的点就是t组数据中每一组数据的初始化…

#include <bits/stdc++.h>
using namespace std;
int n;
int a[3001];
int counter = 1;
int ans = 0, flag = 0;

void dfs (int now, int tar, int con) {
	for (int i = now; i <= n; i++) {
		ans += a[i];
		if (ans == tar) {
			con++;
			ans = 0;
			if (i == n) 
				flag = 1;
		}
	}
	if (flag == 1)
		counter = max(counter, con);
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		counter = 1;
		int sum = 0;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		for (int i = 1; i <= n; i++) {
			sum += a[i];
			ans = 0, flag = 0;
			dfs(i + 1, sum, 1);
		}
		cout << n - counter << endl;
	}
	return 0;
}