题解 P6375

1kri · 2020-04-12 06:57:18 · 题解

GF官方题解

首先爆切50pts，依照题意模拟然后加上记忆化就行了。

从最高点dfs，记录当前位置与是否进行过 2 操作，每次先枚举可能情况然后转移就行了。

50pts代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
#define mod 998244353
using namespace std;
int n,a[1005],mx,mn=2e9;
int f[1005][2];
inline int pw(int a,int p){
    if (p==0)return 1;
    int t=pw(a,p/2);
    t=t*t%mod;
    if (p%2==1)t=t*a%mod;
    return t;
}
inline int inv(int a){
    return pw(a,mod-2);
}
inline int dfs(int now,int flag){
    if (a[now]==mn)return 0;
    if (f[now][flag]!=-1)return f[now][flag];
    int tot=0,s=0;
    for (int i=1;i<=n;i++){
        if (i==now)continue;
        if (a[i]<a[now])tot++;
        else if (a[i]==a[now]&&flag==0)tot++;
    }
    int _inv=inv(tot);
    for (int i=1;i<=n;i++){
        if (i==now)continue;
        if (a[i]<a[now])s+=_inv*(dfs(i,0)+abs(now-i)),s%=mod;
        else if (a[i]==a[now]&&flag==0)s+=_inv*(dfs(i,1)+abs(now-i)),s%=mod;
    }
    return f[now][flag]=s;
}
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++)cin>>a[i],mx=max(mx,a[i]),mn=min(mn,a[i]);
    memset(f,-1,sizeof(f));
    for (int i=1;i<=n;i++){
        if (a[i]==mx){
            cout<<dfs(i,0)<<endl;
            return 0;
        }
    }
    return 0;
}

然后考虑满分dp，先按高度排序，然后相同高度一起转移。

有两种转移情况：相同高度与不同高度。

设 g_{i} 表示由不同高度转移，f_{i} 表示两种转移均可。