2019多校第一场 HDU6578 - Blank（DP，思维，滚动数组优化空间）

链接：HDU6578 - Blank

题意：

有 n (≤100) 个格子，向其中填入 0、1、2、3 这4个数，但是有 m (≤100) 个限制

限制 l r x ：表示 l ~ r 的格子内不同的数的个数为x

问一共有多少种填入方案？

分析：

构建 dp[i][j][k][t][cur]：i,j,k,t 分别表示0,1,2,3出现的最后位置，cur表示填到了第 cur 个格子

根据已求得的 dp[i][j][k][t][cur-1] 可以得到以下状态转移方程（下一位分别填0,1,2,3）：
$$\begin{gathered} dp[cur][j][k][t][cur]=dp[cur][j][k][t][cur]+dp[i][j][k][t][cur?1] \\ dp[i][cur][k][t][cur]=dp[i][cur][k][t][cur]+dp[i][j][k][t][cur?1] \\ dp[i][j][cur][t][cur]=dp[i][j][cur][t][cur]+dp[i][j][k][t][cur?1] \\ dp[i][j][k][cur][cur]=dp[i][j][k][cur][cur]+dp[i][j][k][t][cur?1] \end{gathered}$$

这样对于每一个限制，当 cur == r 时，根据 0,1,2,3出现的最后位置i,j,k,t 是否 >= l，可以得出有 几个不同的数，若不等于x，则dp值变为0。

空间复杂度 O(N⁵)，时间复杂度 O(N⁵)

时间和空间复杂度都达到了5方，要进行优化。

优化①

可以发现因为 i,j,k,t 表示某个数最后一次出现的位置，那么一定有一个是等于 cur 的，而且互不相等（除非为0，即尚未填入）

那么就可以构建 dp[i][j][k][cur] ，其中 i < j < k < cur （若为0可等于）： 只知道 i, j, k, cur 是不同的数最后出现的位置，且i < j < k < cur （并不需要知道 i,j,k,cur对应的填入数是哪个，因为这并不影响对限制的判断）

根据已求得的 dp[i][j][k][cur-1]，得到新的状态转移方程为：（注意这里是i<j<k<cur-1 )
$$\begin{gathered} dp[j][k][cur?1][cur]=dp[j][k][cur?1][cur]+dp[i][j][k][cur?1] \\ dp[i][k][cur?1][cur]=dp[i][k][cur?1][cur]+dp[i][j][k][cur?1] \\ dp[i][j][cur?1][cur]=dp[i][j][cur?1][cur]+dp[i][j][k][cur?1] \\ dp[i][j][k][cur]=dp[i][j][k][cur]+dp[i][j][k][cur?1] \end{gathered}$$
分别表示 将最后一次出现位置为 i, j, k ,cur-1的数填入第cur个格子中

这样时间复杂度和空间复杂度都优化到 O(N⁴)，时间勉强可以，但是空间还是过大了。

优化②

可以发现 dp[][][][cur] 其实只和 dp[][][][cur-1] 有关，那么就可以用滚动数组再节省一下空间

构建 dp[i][j][k][2]，得到状态转移方程：
$$\begin{gathered} dp[j][k][cur?1][now]=dp[j][k][cur?1][now]+dp[i][j][k][pre] \\ dp[i][k][cur?1][now]=dp[i][k][cur?1][now]+dp[i][j][k][pre] \\ dp[i][j][cur?1][now]=dp[i][j][cur?1][now]+dp[i][j][k][pre] \\ dp[i][j][k][now]=dp[i][j][k][now]+dp[i][j][k][pre] \end{gathered}$$

注意： 因为这里是累加，所以用滚动数组时，dp[i][j][k][pre]用完以后要清空！

最终空间复杂度为O (2*N³)，时间复杂度 O(N⁴)

以下代码：

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int INF=0x3f3f3f3f;
const LL MOD=998244353;
const int maxn=100+10;
int main()
{
    int T;scanf("%d",&T);while(T--){
    int n,m;vector<PII> lim[maxn];scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){
    int l,r,x;scanf("%d %d %d",&l,&r,&x);lim[r].push_back(PII(l,x));   //以r分类存入限制}LL dp[maxn][maxn][maxn][2]={
    0};int now=1,pre=0;dp[0][0][0][pre]=1;for(int cur=1;cur<=n;cur++){
    for(int k=0;k<max(cur-1,1);k++)   //只有等于0时，i,j,k,cur才存在相等for(int j=0;j<max(k,1);j++)   //否则满足 i<j<k<curfor(int i=0;i<max(j,1);i++){
    dp[j][k][cur-1][now]=(dp[j][k][cur-1][now]+dp[i][j][k][pre])%MOD;dp[i][k][cur-1][now]=(dp[i][k][cur-1][now]+dp[i][j][k][pre])%MOD;dp[i][j][cur-1][now]=(dp[i][j][cur-1][now]+dp[i][j][k][pre])%MOD;dp[i][j][k][now]=(dp[i][j][k][now]+dp[i][j][k][pre])%MOD;dp[i][j][k][pre]=0;   //用完记得要清空}for(int k=0;k<max(cur,1);k++)for(int j=0;j<max(k,1);j++)for(int i=0;i<max(j,1);i++){
    for(int p=0;p<lim[cur].size();p++){
    PII t=lim[cur][p];               //cur是一定在[l,r]内的if((i>=t.first)+(j>=t.first)+(k>=t.first)+1!=t.second)dp[i][j][k][now]=0;}}swap(now,pre);}//求和当cur==n时的dp值，即为最终答案LL ans=0;for(int k=0;k<max(n,1);k++)for(int j=0;j<max(k,1);j++)for(int i=0;i<max(j,1);i++)ans=(ans+dp[i][j][k][pre])%MOD; //因为最后now和pre多换了一次，所以这里是preprintf("%lld\n",ans);}return 0;
}