考虑枚举最终的颜色 $X$。

不难发现，每一段连续的位置只会出现两种情况：

• 直接被 $X$ 覆盖。
• 先被区间最小值覆盖，再被 $X$ 覆盖。

对两种情况分别使用区间 DP 即可。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
long long d1[312][312], d2[312], d3[312];
int c[312], cc[312][312], cs[312], f[312];
int main()
{
	int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        long long ans = 0x3f3f3f3f3f3f3f3fll;
        for (int i = 1; i <= n; i++)
        {
            cin >> c[i];
            cs[i] = cs[i - 1] + c[i];
            cc[i][i] = c[i];
            for (int j = 1; j <= i - 1; j++)
                cc[j][i] = min(cc[j][i - 1], c[i]);
        }
        memset(d1, 0, sizeof d1);
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
            {
                int mx = 1e9, mc = 0;
                long long sum = 0;
                for (int k = i; k <= j; k++)
                {
                    sum += c[k];
                    if (c[k] < mx) mx = c[k], mc = 0;
                    if (c[k] == mx) mc++;
                }
                d1[i][j] = mx * (sum - 1ll * mc * mx);
            }
        for (int i = 1; i <= n; i++)
        {
            memset(d2, 0x3f, sizeof d2);
            memset(d3, 0x3f, sizeof d3);
            memset(f, 0, sizeof f);
            for (int j = 1; j <= n; j++)
            {
                f[j] = f[j - 1];
                if (c[i] == c[j]) f[j]++;
            }
            d2[0] = 0;
            for (int j = 0; j <= n - 1; j++)
            {
                for (int k = j + 1; k <= n; k++)
                {
                    long long x;
                    x = d2[j] + d1[j + 1][k] + 1ll * cc[j + 1][k] * c[i] * (k - j);
                    d2[k] = min(d2[k], x);
                    x = d3[j] + d1[j + 1][k] + 1ll * cc[j + 1][k] * c[i] * (k - j);
                    d3[k] = min(d3[k], x);
                    if (f[k] == f[j]) continue;
                    x = d2[j] + 1ll * c[i] * (cs[k] - cs[j] - 1ll * c[i] * (f[k] - f[j]));
                    d3[k] = min(d3[k], x);
                    x = d3[j] + 1ll * c[i] * (cs[k] - cs[j] - 1ll * c[i] * (f[k] - f[j]));
                    d3[k] = min(d3[k], x);
                }
            }
            ans = min(ans, d3[n]);
        }
        cout << ans << endl;
    }
	return 0;
}