CodeForces

CF1462D Add to Neighbour and Remove

题目大意：

给定长度为n的序列a，每次操作可以选择相邻的数合并为一个数，求使得序列中所有元素相同的最少操作数量。

思路：

不难想到我们可以通过前缀和来加速合并的过程。

答案一定有解，即下界为0，上界为序列长度n-1。

那么我们可以考虑一个(O(n^2))的算法，因为要求最终的序列每个元素相同，也就相当于把原序列分成若干段，每一段的和相同，所以我们可以O(n)枚举第一段的长度，再O(n)考察后面是否能得到sum相同的若干段。

Code:

import java.util.Scanner;

public class Main {
    public static final int N = 3010;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TestCase = sc.nextInt();
        for (int Ts = 0; Ts < TestCase; Ts++) {
            int ans = 0;
            int n = sc.nextInt();
            int[] a = new int[N];
            int[] pre = new int[N];
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
                pre[i] = pre[i - 1] + a[i];
            }
            for (int i = 1; i <= n; i++) {
                int tmpSum = 0;
                boolean ok = false;
                for (int j = 1; j <= n; j++) {
                    tmpSum += a[j];
                    ans++;
                    if (tmpSum == pre[i]) {
                        ans--;
                        tmpSum = 0;
                        if (j == n) {
                            ok = true;
                            break;
                        }
                    } else if (tmpSum > pre[i]) {
                        break;
                    }
                }
                if (ok) {
                    System.out.println(ans);
                    break;
                } else {
                    ans = 0;
                }
            }
        }
    }
}