P9344 去年天气旧亭台

· · 题解

注意，所有的 a_i 都是正数。

对于第一档分，10 pts，是给暴力的。

对于第二档分，可以考虑一个 dp，dp_i 表示 消完 1 到 i 所要的代价最小，那就从当前的 i 往前找，找到能消去的（颜色相同）去更新 dp_i 的值，方程是：

dp[i]=min(dp[i],a[i]+a[j]+dp[j-1])

时间是 O(t\times n^2) 。

接下来看正解：

分两类讨论。

对于这种情况的话，直接选择 [1,n] 这个区间消去即可。代价为 a_1+a_n。这样做是最优的，因为 1 和 n 两个位置作为首尾，消去的时候这两个位置必选，那么就必然含有 a_1 和 a_n，加上如果中间选择一些辅助 a_i 进行消去，必然不如第一种消去方法优秀。

所以我们有结论，对于 l,r，如果 c_l=c_r，那么消去这个区间的最小代价就一定是 a_l+a_r。

首先有的一个结论是，必然会存在至少一个 c_i 和 c_{i+1}，使得 c_i 等于 c_1，c_n 等于 c_{i+1}。(1\le i \le n-1)

考虑采用反证法证明，如果不存在的话，c_2 必然会等于 c_1（如果不等于 c_1 的话就符合上面的情况了。）以此类推， c_{n-1}=c_1，但是这样的话 c_n=c_n,c_1=c_{n-1}，也就是 [1,n-1] 和 [n,n] 两个区间，矛盾。故得证。

所以我们可以找到至少一组 c_1=c_i,c_{i+1}=c_n 的情况，根据第一种情况的结论，那么最小值就是 (a_1+a_i)+(a_{i+1}+a_n)。O(n) 的时间扫一遍找这个值的最小就好。

时间为 O(t \times n)。

#include<bits/stdc++.h>
using namespace std;
const int N =5e6+10;
#define int long long
int a[N],c[N];
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>c[i];
        if(c[1]==c[n])
        {
            cout<<a[1]+a[n]<<endl;
            continue;
        }
        int ans=LONG_LONG_MAX;
        for(int i=1;i<n;i++)
            if(c[i]==c[1]&&c[i+1]==c[n])
                ans=min(ans,a[i]+a[1]+a[n]+a[i+1]);
        cout<<ans<<endl;
    }
    return 0;
}