UVA12141 Line Chart 题解

是青白呀 · 2023-09-22 15:25:37 · 题解

题目翻译

小 F 打过 n 场比赛，对于第 i 场比赛，我们给出两个参数 s_i 和 p_i，表示这场比赛的时间，和这场比赛后小 F 的比赛分。据此，小 F 以 s_i 为横坐标，p_i 为纵坐标绘制出折线统计图，来表示他比赛分变化的情况。

若一场比赛在折线图上的对应点 i 满足 2 \leq i \leq n，且满足下列条件中的任意一个，则我们称之为“峰值点”。

小 F 认为一个有 k 个峰值点的折线图是美丽的。所以他会删去一些点，并将剩下的点重新顺次连接起来，形成一张新的美丽的折线图。对于新的折线图上的点，他不会使得相邻的两个点的纵坐标相同。请问小 F 最终能得到的合法的美丽的折线图有多少种？

注意：我们认为两种折线图是不同的，当且仅当两张图上各个点的纵坐标依次排列形成的序列不同。

分析

计数问题考虑 dp。首先显然我们可以按 s_i 排序，将删一些点转为按顺序选择一些 p_i。

比较显然的是，我们可以设 dp_{i,j} 表示选了第 i 个点，现在形成的折线图上有 j 个峰值点的方案数。由于峰值点是否形成与第 i 个点和上一个选择的点的大小关系有关，故更改状态为 dp_{i,j,0/1/2}，其中 0 表示 p_i 小于上一个选择的值，1 表示 p_i 大于上一个选择的值，2 表示 p_i 是折线图上被选择的第一个值，再前面没有点。

转移比较显然。

需要注意的是，由于题目中对折线图不同的定义没有考虑点的横坐标，我们发现对于两个点 k_1 和 k_2，若 p_{k_1}=p_{k_2}，我们不能从两个点一起转移，这样会算重。贪心地，我们发现靠后的点一定覆盖了靠前的点的所有情况，所以对于每个相同的 p 值，我们从 i 之前的最后一次出现的位置进行转移即可。

直接转移的复杂度是 O(n^2k)，考虑优化转移。发现我们的转移是在求一个值域范围内的和，于是可以以权值为下标，用树状数组维护答案，对每个峰值点数目和大小关系情况都开一个树状数组，每更新完 i 点的答案，就在对应树状数组的 p_i 下标处单点修改即可。这样保证了树状数组上最新的答案将以前的答案直接覆盖，不会算重。

注意当 k=0 时，还要加上一个点都不选的一种情况。

优化后时间复杂度为 O(nk\log n)。

Code

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define mp make_pair
#define fir first
#define sec second
#define pii pair<int,int>
#define lowbit(x) x&-x
#define ctl(x) floor(log2(x))
#define ppc(x) __builtin_popcount(x)
#define qingbai666 qwq
using namespace std;
typedef long long ll;
const int N=10055,M=55,mo=1000000,inf=1e9+7;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int cases;
int n,m,cntv;
pii a[N];
struct BIT{
    int t[N],val[N];//权值BIT，下标离散化. 
    void add(int x,int v){
        v=(v%mo+mo)%mo;
        for(int i=x;i<=cntv;i+=lowbit(i))
            t[i]+=v,t[i]%=mo;
    }
    void modify(int x,int v){
        add(x,v-val[x]);
        val[x]=v;
    }
    int query(int x){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))
            ret+=t[i],ret%=mo;
        return ret;
    }
}T[M][3];
int dp[N][M][3],v[N];
void solve(int tms){
    read(n),read(m);
    rep(i,0,n){
        rep(j,0,m){
            rep(k,0,2)
                dp[i][j][k]=T[j][k].t[i]=T[j][k].val[i]=0;
        }
    }
    cntv=0;
    rep(i,1,n)
        read(a[i].fir),read(a[i].sec),v[++cntv]=a[i].sec;
    sort(a+1,a+n+1),sort(v+1,v+cntv+1),cntv=unique(v+1,v+cntv+1)-v-1;
    rep(i,1,n)
        a[i].sec=lower_bound(v+1,v+cntv+1,a[i].sec)-v;
    int ans=0;
    rep(i,1,n){
        rep(j,0,m){
            if(j==0)dp[i][j][2]=1;
            dp[i][j][0]+=(j>=1?(T[j-1][1].query(cntv)-T[j-1][1].query(a[i].sec)):0);
            dp[i][j][0]+=(T[j][2].query(cntv)-T[j][2].query(a[i].sec))+(T[j][0].query(cntv)-T[j][0].query(a[i].sec));
            dp[i][j][1]+=T[j][1].query(a[i].sec-1)+T[j][2].query(a[i].sec-1);
            dp[i][j][1]+=(j>=1?T[j-1][0].query(a[i].sec-1):0);
            dp[i][j][0]=(dp[i][j][0]%mo+mo)%mo,dp[i][j][1]=(dp[i][j][1]%mo+mo)%mo;
            rep(k,0,2)
                T[j][k].modify(a[i].sec,dp[i][j][k]);
        }
    }
    rep(k,0,2)
        ans+=T[m][k].query(cntv);
    if(m==0)ans++;//删完，一个不剩 
    printf("Case %d: %d\n",tms,ans%mo);
}
int main(){
    read(cases);
    rep(i,1,cases)
        solve(i);
    return 0;
}