[2019HDU多校第一场][HDU 6578][A. Blank]

本是古典何须时尚 2021-11-01 06:10 239阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6578][http_acm.hdu.edu.cn_showproblem.php_pid_6578]

题目大意：长度为\\(n\\)的数组要求分别填入\\(\\\{0,1,2,3\\\}\\)四个数中的任意一个，有\\(m\\)个限制条件：区间\\(\[l,r\]\\)中出现的数字种数恰好为\\(x\\)，求方案数

题解：f\[i\]\[j\]\[k\]\[cur\]表示四个数最后出现的位置经过排序后为\\(i,j,k,cur\\)的方案数，暴力转移即可，其中最后一维需要滚动数组节省空间

对于限制条件可以用vector存下来，每次循环对右端点为当前点的限制条件进行判断即可

虽然要套四个\\(for\\)，但是由于有顺序限制，所以执行次数大约为\\(\\frac\{n^4\}\{24\}\\)，加上本题的运算简单，常数较小，因此基本不会出现TLE的情况

但是还是要吐槽一句出题人把这场比赛的时间设的好死啊...开个3s应该也不至于放假算法过吧orz

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 101
     4 #define mp make_pair
     5 #define MOD 998244353
     6 int T,n,m,l,r,x,f[N][N][N][2],ans;
     7 vector<pair<int,int>>d[N];
     8 void init()
     9 {
    10     ans=0;
    11     scanf("%d%d",&n,&m);
    12     for(int i=1;i<=n;i++)
    13       {
    14       d[i].clear();
    15       d[i].push_back(mp(i,1));
    16       }
    17     for(int i=1;i<=m;i++)
    18       {
    19       scanf("%d%d%d",&l,&r,&x);
    20       d[r].push_back(mp(l,x));
    21       }
    22     memset(f,0,sizeof(f));
    23     f[0][0][0][0]=1;
    24     for(int cur=1;cur<=n;cur++)
    25       {
    26       int o=cur&1;
    27       for(int i=0;i<=cur;i++)
    28         for(int j=i;j<=cur;j++)
    29           for(int k=j;k<=cur;k++)
    30             f[i][j][k][o]=0;
    31       for(int i=0;i<=cur;i++)
    32         for(int j=i;j<=cur;j++)
    33           for(int k=j;k<=cur;k++)
    34             {
    35             (f[j][k][cur-1][o]+=f[i][j][k][o^1])%=MOD;
    36             (f[i][k][cur-1][o]+=f[i][j][k][o^1])%=MOD;
    37             (f[i][j][cur-1][o]+=f[i][j][k][o^1])%=MOD;
    38             (f[i][j][k][o]+=f[i][j][k][o^1])%=MOD;
    39             }
    40       for(int i=0;i<=cur;i++)
    41         for(int j=i;j<=cur;j++)
    42           for(int k=j;k<=cur;k++)
    43             for(auto pi:d[cur])
    44               {
    45               l=pi.first,r=cur,x=pi.second;
    46               if((i>=l)+(j>=l)+(k>=l)+(cur>=l)!=x)
    47                 f[i][j][k][o]=0;
    48               }
    49       }
    50     for(int i=0;i<=n;i++)
    51       for(int j=i;j<=n;j++)
    52         for(int k=j;k<=n;k++)
    53           (ans+=f[i][j][k][n&1])%=MOD;
    54     printf("%d\n",ans);
    55 }
    56 int main()
    57 {
    58     scanf("%d",&T);
    59     while(T--)init();
    60 }

代码中对vector的初始化其实是没必要额外push\_back的，写的时候为了保险就加上去了（虽然差点导致TLE）

这竟然是我博客里的第一道纯DP题...?

转载于:https://www.cnblogs.com/DeaphetS/p/11229389.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6578]: http://acm.hdu.edu.cn/showproblem.php?pid=6578
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/06ebb085b2a846cbafcea47d7c9c2a79.png