URAL1696 Salary for Robots

题目戳这里。
最长下降子序列单调队列求法。
(f_{i,j,k})表示考虑前(i)个数，(g_1 = j,g_2 = k)的方案数。转移：
[f_{i,j,k} = sum_{p = k+1}^{j}f_{i-1,p,k}+sum_{p=0}^kf_{i-1,j,p}]
二维前缀和优化。复杂度(O(NK^2))。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxk = 201;
int f[2][maxk][maxk],N,K,rhl,ans;
int main()
{
freopen("1696.in","r",stdin);
freopen("1696.out","w",stdout);
scanf("%d %d %d",&N,&K,&rhl);
for (int i = 1;i <= K;++i) f[1][i][0] = 1;
for (int p = 2,now = 0,last = 1,inc;p <= N;++p,swap(now,last))
{
for (int i = 1;i <= K;++i)
{
for (int j = i-1;j >= 0;--j)
{
f[last][i][j] += f[last][i][j+1];
if (f[last][i][j] >= rhl) f[last][i][j] -= rhl;
}
for (int j = 0;j < i;++j)
{
f[last][i][j] += f[last][i-1][j];
if (f[last][i][j] >= rhl) f[last][i][j] -= rhl;
}
}
memset(f[now],0,sizeof f[now]);
for (int i = 1;i <= K;++i)
for (int j = 0;j < i;++j)
{
f[now][i][j] = f[last][i][j]-f[last][j][j]-f[last][i][j+1]+f[last][j][j+1];
while (f[now][i][j] >= rhl) f[now][i][j] -= rhl;
while (f[now][i][j] < 0) f[now][i][j] += rhl;
if (j)
{
inc = f[last][i][0]-f[last][i-1][0]-f[last][i][j+1]+f[last][i-1][j+1];
while (inc >= rhl) inc -= rhl; while (inc < 0) inc += rhl;
f[now][i][j] += inc; if (f[now][i][j] >= rhl) f[now][i][j] -= rhl;
}
}
}
for (int i = 1;i <= K;++i)
for (int j = 0;j < i;++j)
{
ans += f[N&1][i][j];
if (ans >= rhl) ans -= rhl;
}
printf("%dn",ans+1);
fclose(stdin); fclose(stdout);
return 0;
}