题解：CF2004F Make a Palindrome

· · 题解

题意简述

给定一个长为 n 的数组，有如下两种操作

  1. 将相邻两个数合并，合并的数为两个数的和。
  2. 将一个数 x 拆解，使得拆解的两个数均为正数且和为 x。

求将 n 数组的每个子串变为回文串的最小代价和。

思路

考虑单个区间，显然的，一个长为 k 的区间，经过 k-1 次操作必然能变成一个回文串

那什么时候可以做优化呢？

注意到，当一个前缀 1 到 l 和一个后缀 r 到 n 的和相等的时候，那么我们把这个前缀和这个后缀合并完之后就不需要接着把它们和中间的数合并，故操作次数会减少 2。

可是我们发现，在 [1,3,2,4] 这个例子中，前缀和后缀相等却只减少了 1 次操作，这就很麻烦，考虑如何把这个限制去掉。

发现第一种操作次数减少 2 的操作，可以表示为 [l_1,r_1] 和 [l_2,r_2] 贡献的 1 次以及 [l_1,l_2-1] 和 [r_1+1,r_2] 贡献的 1 次。

这样就好做了，考虑把贡献拆开，每次只要遇到 sum 重复的 [l_x,r_x] ，那么他在与 [l_1,r_1] 到 [l_{x-1},r_{x-1}] 这些 sum 相同的区间作为某个区间两端都会对答案 -1，所以答案减去 x-1。

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[2005];
map<int,int>mp;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        mp.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int sum=0;
            for(int j=i;j<=n;j++)
            {
                sum+=a[j];
                ans+=j-i-mp[sum];
                mp[sum]++;
            }
        }
        printf("%d\n",ans);
    }
}