斜率优化

某次比赛中需要斜率优化发现写得极不顺畅。。。总结一个模板化的东西以后照抄。
SDOI2016 征途为例,题目要求的就是将n个数字的数组分成至多m段,使得每一段的和的平方的总和最小。

f[p][i]表示将前i个数字分成p段的和的最小值,转移显然。
斜率优化:对于一个点i,决策点k_1优于决策点k_2(k_1 < k_2 < i)

\begin{aligned}
f[p-1][k_1]+(s[i]-s[k_1])^2 & < f[p-1][k_2]+(s[i]-s[k_2])^2\\
\frac {(f[p-1][k_1]+s^2[k_1])-(f[p-1][k_2]+s^2[k_2])}{s[k_1]-s[k_2]} & > 2s[i]
\end{aligned}

也就是,当上面的不等式中间为\le时,k_1就可以被扔掉,扔掉之后,队首两个元素的斜率应该上升,直到 > 2s[i]
因此按照这个式子,由于s[i]是不下降的,所以维护决策点连线斜率单增的队列,也就是决策点构成的下凸壳,然后维护下凸壳可以用计算几何的方法。。。
如果某个a[i]=0,那么s[i]=s[i-1],也就是ii-1决策点的横坐标相同,那么i点的纵坐标必定\le i-1点的纵坐标。如果纵坐标相等,要注意去掉这个重复点,否则,放在维护下凸壳的算法里,这种情形也能正确处理。

const int XN=3000+11;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN],f[XN][XN],sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        f[1][i]=sum[i]*sum[i];
    }
    for(int p=2;p<=m;++p) {
        static int Q[XN],head,tail;

        Q[head=0]=p-1;tail=1;
        for(int i=p;i<=n;++i) {
            auto Calc=[&](int t)->int {
                return f[p-1][t]+(sum[i]-sum[t])*(sum[i]-sum[t]);
            };

            auto TurnRight=[&](std::array<int,3> id)->bool {
                std::array<long long,3> x,y;
                for(int i=0;i<3;++i) {
                    x[i]=sum[id[i]];
                    y[i]=f[p-1][id[i]]+sum[id[i]]*sum[id[i]];
                }
                return (x[1]-x[0])*(y[2]-y[1])-(x[2]-x[1])*(y[1]-y[0])<=0;
            };

            while(tail-head>=2 && Calc(Q[head])>=Calc(Q[head+1]))
                head++; 

            f[p][i]=Calc(Q[head]);

            while(tail-head>=2 && TurnRight({Q[tail-2],Q[tail-1],i}))
                tail--;
            Q[tail++]=i;
        }
    }
    int Ans=f[m][n]*m-sum[n]*sum[n];
    std::cout<<Ans<<'\n';
    return 0;
}

[Codeforces 1131E]String Multiplication

Link

s\cdot t=t+s_1+t+s_2+…+s_n+t
\prod s_i中最长的连续的相同字符组成的字符串的长度。

Solution

L(s,c)sc字符的最长连续长度,则要求的结果就是\max L(\prod s_i,c),c\in[‘a’,’z’]
实时维护L(\prod s_i,c)。当读入一个t字符串时,分如下情况讨论:
1. t中的字符全部相同,设为x

L(\prod s_i\cdot t,c)=
\begin{cases}
(L(\prod s_i,c)+1)({\rm len}(t)+1)-1,&c=x\\
1,&c\not=x,c\in \prod s_i\\
0,&\text{otherwise}
\end{cases}
  1. t的字符不全部相同
    t的最长相同前缀的长度为p,最长相同后缀为s
    再分情况

    1. {\rm first}(t)={\rm last}(t)=x
      对于c\not=x
    L(\prod s_i\cdot t,c)=
    \begin{cases}
    1,&c\in\prod s_i\\
    0,&\text{otherwise}
    \end{cases}

    对于x

    L(\prod s_i\cdot t,x)=
    \begin{cases}
    p+s+1,&x\in\prod s_i\\
    \max(p,s),&\text{otherwise}
    \end{cases}
    1. {\rm first}(t)\not={\rm last}(t)
      与上相似。

Code

const int XN=1e5+11;
typedef std::array<long long,26> Record;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    std::string s;std::cin>>s;
    auto Do=[&](std::string s)->std::tuple<long long,long long,Record> {
        s+=' ';
        long long pref=-1,suf=-1;
        Record mxl;
        for(int i=0;i<26;++i)
            mxl[i]=0;
        for(size_t i=1,len=1;i<s.length();++i)
            if(s[i]==s[i-1])
                len++;
            else {
                if(pref==-1)
                    pref=len;
                if(i==s.length()-1)
                    suf=len;
                Enlarge(mxl[s[i-1]-'a'],(long long)len);
                len=1;
            }
        if(pref==s.length()-1)
            suf=0;
        return {pref,suf,mxl};
    };
    Record smxl;long long pre,suf;
    static bool has[26];
    for(size_t i=0;i<s.length();++i)
        has[s[i]-'a']=1;
    std::tie(pre,suf,smxl)=Do(s);
    for(int i=2;i<=n;++i) {
        std::string t;std::cin>>t;
        Record tmxl;
        std::tie(pre,suf,tmxl)=Do(t);
        if(!suf) {
            long long temp=(smxl[t[0]-'a']+1)*(t.length()+1)-1;
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            Enlarge(smxl[t[0]-'a'],temp);
        } else {
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            if(t[0]==t[t.length()-1]) {
                long long temp=std::max(pre,suf);
                if(has[t[0]-'a']) {
                    temp=pre+suf+1;
                }
                smxl[t[0]-'a']=temp;
            } else {
                if(has[t[0]-'a']) {
                    smxl[t[0]-'a']=pre+1;
                }
                if(has[t[t.length()-1]-'a']) {
                    smxl[t[t.length()-1]-'a']=suf+1;
                }
            }
        }
        for(size_t i=0;i<t.length();++i)
            has[t[i]-'a']=1;
        for(int c=0;c<26;++c)
            Reduce(smxl[c],(long long)1e9);
        for(int c=0;c<26;++c)
            Enlarge(smxl[c],tmxl[c]);
    }
    std::cout<<*std::max_element(smxl.begin(),smxl.end())<<'\n';
    return 0;
}

Tips

题意理解反了浪费了半个小时。。
题目给了答案\le 10^9,就直接暴力取min就好了。

for_each,generate,transform

std::for_each

template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

std::generate

template <class ForwardIterator, class Generator>
  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
  while (first != last) {
    *first = gen();
    ++first;
  }
}

std::transform

template <class InputIterator, class OutputIterator, class UnaryOperator>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperator op)
{
  while (first1 != last1) {
    *result = op(*first1);  // or: *result=binary_op(*first1,*first2++);
    ++result; ++first1;
  }
  return result;
}