P7070 题解

P7070

思路

发现不同的订单之间只有 $t$ 的限制，其他的信息独立。

考虑做 $n$ 遍 dp，然后第 $i$ 次 dp 的初始值由 $i-1$ 次的结果决定。

设 $f_{i,j,k}$ 表示当前在是第 $i$ 秒，做过 $j$ 次梦，上一次做梦在第 $i-k$ 秒。

转移讨论下一秒摸不摸鱼。

$f_{i,j,k} \rarr f_{i+1,j,k+1}\\ f_{i,j,k} \rarr f_{i+1,j+1,0},k\ge t$

每一位都开 $q$ 的话是 $O(nq^3)$ 的，考虑优化状态。

对于第二维，前 $i$ 秒的做梦次数不超过 $\frac{i-1}{t+1}+1$。所以把第二维缩小到 $\frac{n}{t}$ 规模 。

对于第三维，观察第二个转移，发现 $k>t$ 的情况等价与 $k=t$ 的情况，因为我们只关心当前能不能做梦。于是把第三维缩小到 $t$ 规模。

时间复杂度缩小为是 $O(nq\frac qt t)$，也就是 $O(nq^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
#define N 2005
#define M 305
#define rep(i,x,y) for(int i=x;i<=y;i++)
int n,T,mod;
int a[N],b[N];
int f[2][M][M];
inline void Add(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
void solve()
{
    cin>>n>>T>>mod;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        b[i]=a[i]-b[i];
    }
    f[0][0][T]=1;int o=0;
    for(int id=1;id<=n;id++)
    {
        rep(j,0,b[id-1]) rep(k,0,T)
            f[o^1][j][k]=0;
        rep(j,0,b[id-1]) rep(k,0,T)
        {
            Add(f[o^1][0][k],f[o][j][k]);
            f[o][j][k]=0;
        }
        o^=1;
        for(int i=0;i<a[id];i++,o^=1)
        {
            rep(j,0,min(b[id],i/(T+1)+1))
                rep(k,0,T) f[o^1][j][k]=0;
            rep(j,0,min(b[id],(i-1)/(T+1)+1))
            {
                rep(k,0,T) if(f[o][j][k])
                    Add(f[o^1][j][min(T,k+1)],f[o][j][k]);
                if(j<b[id]) Add(f[o^1][j+1][0],f[o][j][T]);
            }
        }
    }
    int ans=0;
    rep(j,0,b[n]) rep(k,0,T)
        Add(ans,f[o][j][k]);
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
}

此题为这场比赛 B 题。