题解 P3336 【[ZJOI2013]话旧】

· · 题解

首先考虑方案。

我们用dp_{i,0/1}表示函数图象到(x_i,y_i)点，前一段线段的方向是1/-1的方案数

设前一个节点与当前节点坐标分别为(x1,y1),(x2,y2)考虑以下几种情形：

  3. 设len=x2-x1-y1-y2 如果len< 0只有先向上后向下一种方案 否则分别考虑前后上升或下降的四种情况。 可以发现会形成一种类似锯齿的形状，锯齿的边可以移动。先上后下本质上就是所有上升边移到左边得到的。cnt个锯齿的边的移动方案可以表示为2^{cnt}

然后考虑最大值，最大值也可以类似的转移。不存在方案时这个值被赋为-inf。从前面上升后面下降的方式得到的一定是最优的，但是如果这样的方案不符合转移时，就要考虑其他情况。包括但不限于先向下，然后向上向下，向上向下向上等。每一种最大值一定是某一段上升再下降的顶点或是y1,y2。

代码如下

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<cmath>
#define PII pair<int,int>
#define pb push_back
#define ep emplace_back
#define mp make_pair
#define fi first
#define se second
//#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return f==1?x:~x+1;
}
inline void print(int x){
    if(x<0) putchar('-'),x=~x+1;
    if(x>=10) print(x/10);
    putchar((x%10)|48);
}
const int mod=19940417;
int n,k;
set<PII>st;
PII a[1000010];
int dp[1000010][2],mxn[1000010][2];// 0 up 1 down
int qpow(int x,int k){
    if(k<=0) return 1;
    int res=1;
    while(k){
        if(k&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    } 
    return res;
}
void uad(int &x,int y){
    x=(x+y>=mod?x+y-mod:x+y);
}
int add(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
signed main(){
    n=read(),k=read();
    st.insert(mp(0,0));
    st.insert(mp(n,0));
    for(int i=1;i<=k;++i){
        int x=read(),y=read();
        st.insert(mp(x,y));
    }
    int m=0;
    for(auto i:st){
        a[++m]=i;
    }
    memset(mxn,-0x3f,sizeof(mxn));
    dp[1][1]=1;mxn[1][0]=0;
    for(int i=2;i<=m;++i){
        int x1=a[i-1].fi,y1=a[i-1].se;
        int x2=a[i].fi,y2=a[i].se;
        if(x2-x1==y2-y1){
            uad(dp[i][0],dp[i-1][0]);
            mxn[i][0]=max(mxn[i-1][0],y2);
            if(y1==0) uad(dp[i][0],dp[i-1][1]),mxn[i][0]=max(mxn[i-1][1],y2);
        } 
        else if(x2-x1==y1-y2){
            uad(dp[i][1],dp[i-1][1]);uad(dp[i][1],dp[i-1][0]);
            mxn[i][1]=max(max(mxn[i-1][1],mxn[i-1][0]),y2);
        }
        else{
            int len=x2-x1-y1-y2;
            if(len<=0){
                int pre=mxn[i-1][0];
                uad(dp[i][1],dp[i-1][0]);if(y1==0) uad(dp[i][1],dp[i-1][1]),pre=max(pre,mxn[i-1][1]);
                if(dp[i][1])mxn[i][1]=max(pre,(x2+y2-y1-x1>>1)+y1);//x+y=x2-x1,x-y=y2-y1 x=x2+y2-y1-x1
            }
            if(len>=0){
                if(len==0){
                    uad(dp[i][0],dp[i-1][0]);uad(dp[i][0],dp[i-1][1]);
                    mxn[i][0]=max(max(mxn[i-1][1],mxn[i-1][0]),y2);
                }
                else{
                    int t,t2;
                    if(dp[i-1][0]>0){
//                      printf("O:%d\n",i);
                        t=max(max(y1==0?mxn[i-1][1]:-0x3f3f3f3f,mxn[i-1][0]),(x2+y2-y1-x1>>1)+y1);
                        t2=max(max(y1==0?mxn[i-1][1]:-0x3f3f3f3f,mxn[i-1][0]),y1+(x2-y2-y1-x1>>1));
                    }
                    else{
//                      printf("i:%d\n",i);
                        t=max(mxn[i-1][1],(x2-x1-y1+y2>>1));//x+y=x2-x1-y1,x-y=y2
                        t2=max(mxn[i-1][1],len>>1);//x+y=x2-x1-y1-y2,x-y=0
                    }
                    int k=add(1ll*dp[i-1][1]*qpow(2,(len>>1)-1)%mod,1ll*dp[i-1][0]*qpow(2,len>>1)%mod);
                    if(y2>0) uad(dp[i][0],k),mxn[i][0]=max(t2,y2);
                    uad(dp[i][1],k);mxn[i][1]=max(t,y2);
                }
            }
        }
        if(!dp[i][0]) mxn[i][0]=-0x3f3f3f3f;
        if(!dp[i][1]) mxn[i][1]=-0x3f3f3f3f;
//      printf("i:%d,mxn:%d,%d\n",i,mxn[i][0],mxn[i][1]);
    }
    printf("%d %d\n",dp[m][1],mxn[m][1]);
}