题解：AT_arc211_c [ARC211C] Forest

· · 题解

题意：

::::info[本文对题面的修改] 把原串 S 写为 01 串的形式，其中 0 代表字符"."，即没有树；1 代表字符"#"，即包含树。 ::::

给定一个长度为 n 的 01 串 S 和数组 R，每次可以选择 S 的一个子串 S_l,S_{l+1},...,S_r，使得左右两端为 0，中间不全为 0，并把 [l,r] 全赋为 0，贡献为 R_l+R_r。

询问：设最大价值和为 sum，有多少个可行的第一次操作可以使得存在一系列操作使价值和达到 sum。

Solution

显然，我们把 S 划分为若干 0/1 连续段，则一段内只有最大值有效，则我们就能将序列的每个连续段用一个二元组 (type,w) 表示，其中 type 为区间类型 0/1，w 为区间最大值。

这样将序列简化完以后，就可以将操作表示为：找到两个类型为 0 的段 i,j，删除 [i,j] 内所有二元组，并用 (0,\displaystyle\max_{k=i}^j w_k) 替换，贡献为 w_i+w_j。

考虑贪心策略，每次只删除一个形如 010 的区间显然是不劣的，不然就可以用更多次操作使得贡献和更大。

那么容易发现，为了将序列清空且每次只能删相邻两个 0，操作次数是固定的，原序列的每一个 0 区间的 w_i 都至少被贡献过一次，而剩下的若干个能贡献进答案的数又总能是全局最大值，只要找到全局最大值所在的区间并每次都用它往外扩展即可，而这样显然最优，所以第一次删的区间必然要包含全局最大值。

因此我们记全局最大值为 mx，cnt_i 为区间 i 的最大值个数，答案即为：

\displaystyle \sum_{i=1}^{m-2} [type_i=0 \land \max(w_i,w_{i+1},w_{i+2})=mx]\times cnt_i\times cnt_{i+2}

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const int N=5e5+5;
char s[N];
int n,m,r[N];
struct node{int tp,x;ll cnt;}t[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        cin>>s[i];
    int mx(0),cnt(0);
    s[0]='&';
    for(int i=1;i<=n;++i){
        scanf("%d",&r[i]);
        if(s[i]!=s[i-1]){
            if(i!=1){
                if(s[i]=='#')t[++m]={0,mx,cnt};
                else t[++m]={1,mx,0}; 
            }
            mx=r[i],cnt=1;
        }
        else if(mx<r[i])mx=r[i],cnt=1;
        else if(mx==r[i])++cnt;
    }
    if(s[n]=='#')t[++m]={1,mx,0};
    else t[++m]={0,mx,cnt};
    int tx(0);
    ll ans(0);
    for(int i=1;i<=m-2;++i)
        if(t[i].tp==0)tx=max(tx,max({t[i].x,t[i+1].x,t[i+2].x}));
    for(int i=1;i<=m-2;++i)
        if(t[i].tp==0&&max({t[i].x,t[i+1].x,t[i+2].x})==tx)ans+=t[i].cnt*t[i+2].cnt;
    printf("%lld",ans);
    return 0;
}

::::