2019 Multi-University Training Contest 1 - 1001 - Blank - dp

http://acm.hdu.edu.cn/showproblem.php?pid=6578

不會做，看題解。

設dp[i][j][k][l]表示4種顏色出現的最后的位置分別是i,j,k,l的方法數，保證i>=j>=k>=l。其實不取=號，因為同一個位置不能放兩個元素，除了開始的若干個比如dp[1][0][0][0]=4。

合法的轉移疊加：
比如
刷新的顏色是i：dp[i+1][j][k][l]+=dp[i][j][k][l]
刷新的顏色是j：dp[i+1][i][k][l]+=dp[i][j][k][l]
刷新的顏色是k：dp[i+1][i][j][l]+=dp[i][j][k][l]
刷新的顏色是l：dp[i+1][i][j][k]+=dp[i][j][k][l]

假如從dp[i][j][k][l]轉移到上述狀態會導致新狀態不滿足約束則不進行這次轉移，就太麻煩了。
由于是dp，其實只要遇到約束區間的右端點R的時候再考慮約束就可以了。

考慮四個數其實是[l,k,j,i]，i肯定就是R，要是l>=L則有恰好4種顏色，否則要是k>=L則恰好3種顏色，否則要是j>=L則恰好2種顏色，否則只有1種顏色。

對每次轉移后新狀態的i維度必定是i+1，對i維度進行滾動節省空間。復雜度是精確的O(n^4+mn^3)，據說很多隊覺得過不了。

還卡memset？？？15組數據還卡memset？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;inline int read() {int x = 0;char c = 0;while(c < '0' || c > '9')c = getchar();while(c >= '0' && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();return x;
}inline void _write(int x) {if(x > 9)_write(x / 10);putchar(x % 10 + '0');
}inline void write(int x) {_write(x);putchar('\n');
}struct Condition {int l, r, x;bool operator<(const Condition &c)const {return r < c.r;}
} con[105];const int mod = 998244353;
int n, m, dp[2][105][105][105], ctop;inline void clear0(int n) {for(int j = 0; j <= n; ++j) {for(int k = 0; k <= j; ++k) {for(int l = 0; l <= k; ++l) {dp[n & 1][j][k][l] = 0;}}}
}inline void clear1(int i, int L) {//清除==1種的for(int j = L - 1 ; j >= 0; --j) {for(int k = j ; k >= 0; --k) {for(int l = k ; l >= 0; --l) {dp[i & 1][j][k][l] = 0;}}}
}inline void clear2(int i, int L) {//清除==2種的for(int j = i ; j >= L; --j) {for(int k = L - 1; k >= 0; --k) {for(int l = k ; l >= 0; --l) {dp[i & 1][j][k][l] = 0;}}}
}inline void clear3(int i, int L) {//清除==3種的for(int j = i ; j >= L ; --j) {for(int k = j ; k >= L; --k) {for(int l = L - 1; l >= 0; --l) {dp[i & 1][j][k][l] = 0;}}}
}inline void clear4(int i, int L) {//清除==4種的for(int j = i ; j >= L ; --j) {for(int k = j ; k >= L ; --k) {for(int l = k ; l >= L; --l) {dp[i & 1][j][k][l] = 0;}}}
}inline void update1(int i) {if(ctop > m || i < con[ctop].r)return;while(ctop <= m && i == con[ctop].r) {//printf("cons %d\n", ctop);int L = con[ctop].l, x = con[ctop].x;++ctop;if(x == 1) {clear2(i, L);clear3(i, L);clear4(i, L);} else if(x == 2) {clear1(i, L);clear3(i, L);clear4(i, L);} else if(x == 3) {clear1(i, L);clear2(i, L);clear4(i, L);} else {clear1(i, L);clear2(i, L);clear3(i, L);}}
}inline void update2(int i, int j, int k, int l) {dp[(i + 1) & 1][j][k][l] += dp[i & 1][j][k][l];if(dp[(i + 1) & 1][j][k][l] >= mod)dp[(i + 1) & 1][j][k][l] -= mod;dp[(i + 1) & 1][i][k][l] += dp[i & 1][j][k][l];if(dp[(i + 1) & 1][i][k][l] >= mod)dp[(i + 1) & 1][i][k][l] -= mod;dp[(i + 1) & 1][i][j][l] += dp[i & 1][j][k][l];if(dp[(i + 1) & 1][i][j][l] >= mod)dp[(i + 1) & 1][i][j][l] -= mod;dp[(i + 1) & 1][i][j][k] += dp[i & 1][j][k][l];if(dp[(i + 1) & 1][i][j][k] >= mod)dp[(i + 1) & 1][i][j][k] -= mod;
}int solve() {ctop = 1;memset(dp[1], 0, sizeof(dp[1]));dp[1][0][0][0] = 4;update1(1);for(int i = 1; i <= n - 1; ++i) {//printf("i=%d\n", i);clear0(i + 1);for(int j = i; j >= 0; --j) {for(int k = j ; k >= 0; --k) {if(k == j && k)continue;for(int l = k ; l >= 0; --l) {if(l == k && l)continue;update2(i, j, k, l);}}}update1(i + 1);for(int j = i; j >= 0; --j) {for(int k = j; k >= 0; --k) {if(k == j && k)continue;for(int l = k ; l >= 0; --l) {if(l == k && l)continue;//printf("dp[%d][%d][%d][%d]=%d\n", i + 1, j, k, l, dp[(i + 1) & 1][j][k][l]);}}}//printf("\n");}int ans = 0;for(int j = n - 1; j >= 0; --j) {for(int k = j ; k >= 0; --k) {for(int l = k ; l >= 0; --l) {ans += dp[n & 1][j][k][l];if(ans >= mod)ans -= mod;}}}return ans;
}
int main() {
#ifdef Yinkufreopen("Yinku.in", "r", stdin);
#endif // Yinkuint T = read();while(T--) {n = read(), m = read();for(int i = 1; i <= m; ++i) {con[i].l = read(), con[i].r = read(), con[i].x = read();}sort(con + 1, con + 1 + m);write(solve());}return 0;
}