HDU多校第一场 1001 Blank —— dp

题目链接：点我啊╭(╯^╰)╮

题目大意：

    长度为 $n$ 的序列，由 $0、1、2、3$ 组成
    限制 $l$ $r$ $x$ ：区间 $[l,r]$ 内有且仅有 $x$ 个不同的数字
    求方案数

解题思路：

    记录每个数字最后出现的位置
    可以通过位置判断区间内数字种类数
    设 $dp[i][j][k][t][pos]$，$i,j,k,t$ 依次为 $0,1,2,3$ 最后出现的位置

    那么状态转移就显而易见：
    $dp[pos][j][k][t][pos]+=dp[i][j][k][t][pos?1]$
    $dp[i][pos][k][t][pos]+=dp[i][j][k][t][pos?1]$
    $dp[i][j][pos][t][pos]+=dp[i][j][k][t][pos?1]$
    $dp[i][j][k][pos][pos]+=dp[i][j][k][t][pos?1]$
    时间复杂度：$O(n^5)$，空间复杂度：$O(n^5)$

    发现每一次转移，都有两个位置都是 $pos$
    也就是当前转移的那个数字最后出现位置一定是 $pos$
    考虑将这两维压缩成一维
    设 $dp[i][j][k][pos]$，$i,j,k,pos$ 为不同数字最后出现的位置，且 $i<j<k<pos$

    那么对于当前的转移 $dp[i][j][k][pos?1]$，状态转移为
    $dp[j][k][pos?1][pos]+=dp[i][j][k][pos?1]$
    $dp[i][k][pos?1][pos]+=dp[i][j][k][pos?1]$
    $dp[i][j][pos?1][pos]+=dp[i][j][k][pos?1]$
    $dp[i][j][k][pos]+=dp[i][j][k][pos?1]$

    对于一个限制 $l$ $r$ $x$，将对应 $dp$ 置为 $0$
    最后一维用滚动优化
    时间复杂度：$O(n^4)$，空间复杂度：$O(2\times n^3)$

核心：优化dp

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int mod = 998244353;
int T, n, m, dp[105][105][105][2]; int main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);vector <pii> lm[105];while(m--){int l, r, x; scanf("%d%d%d", &l, &r, &x);lm[r].push_back(pii(l, x));}memset(dp, 0, sizeof(dp));dp[0][0][0][0] = 1;int now = 1, pre = 0;for(int pos=1; pos<=n; pos++){for(int k=0; k<pos; k++)for(int j=0; j<max(k, 1); j++)for(int i=0; i<max(j, 1); i++){dp[j][k][pos-1][now] = (dp[j][k][pos-1][now] + dp[i][j][k][pre]) % mod;dp[i][k][pos-1][now] = (dp[i][k][pos-1][now] + dp[i][j][k][pre]) % mod;dp[i][j][pos-1][now] = (dp[i][j][pos-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<pos; k++)for(int j=0; j<max(k, 1); j++)for(int i=0; i<max(j, 1); i++)for(auto r : lm[pos]){int num = 1 + (i>=r.first) + (j>=r.first) + (k>=r.first);if(num ^ r.second) dp[i][j][k][now] = 0;}swap(now, pre);}ll ans = 0;for(int k=0; k<n; 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;printf("%lld\n", ans);}
}