题解 P4933 【大师】

2018-10-22 17:12:54


这题v在long long以内也是可以做的

这里提出一种$n^2logn$的有别于官方题解的做法

首先发现一个性质:每个点要作为等差数列的中间部分,则公差最多只有n种

所以我们可以对此下手

QAQ

设$t[i].g[j]$表示高度为i的塔,前面接上公差为j的等差数列有多少种方案,num记录有多少高度为i的塔

于是转移就很显然了,往后加上高度为k的塔的时候,枚举前面的塔是i,有两种方式贡献答案:

  • 直接把i作为等差数列开头($ans+=num$)
  • 把i作为等差数列中间($ans+=t[i].g[k-i]$)

同时把新增的答案更新到k的状态上去即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
using namespace std;
const int N=1010,mod=998244353;
struct Node{map<int,int> g;int num;}t[N];
int n,h[N],B[N],rk[N],up,ans;
map<int,int> Map;
void add(int &a,int b) {a+=b;if(a>=mod) a-=mod;}
int main()
{
    cin>>n;ans=n;
    for(int i=1;i<=n;i++) cin>>h[i],B[i]=h[i];
    sort(B+1,B+n+1);
    up=unique(B+1,B+n+1)-B-1;
    for(int i=1;i<=up;i++) Map[B[i]]=i,rk[i]=B[i];
    for(int i=1;i<=n;i++) h[i]=Map[h[i]];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=up;j++)
        {
            int d=rk[h[i]]-rk[j],res=t[j].num;
            if(t[j].g.find(d)!=t[j].g.end()) add(res,t[j].g[d]);
            if(!res) continue;
            add(ans,res);
            add(t[h[i]].g[d],res);
        }
        t[h[i]].num++;
    }
    return cout<<ans<<endl,0;
}

广告:https://www.cnblogs.com/xzyxzy