1462 D. Add to Neighbour and Remove

1462 D. Add to Neighbour and Remove

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

一开始想不出思路，就知道最差情况是操作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;
}