粉刷匠2（draw.in/draw.out） 有一个4*N的木板需要粉刷，第i行j列的颜色记为A(i, j)。 有256种颜色，记为0..255，为了使得粉刷比较好看，粉刷需要满足如下要求: 1. A(x,y) >= A(x,y-1) 2. 有一些指定的(x1, y1)和(x2, y2)，要求A(x1, y1) = A(x2, y2) 请问有多少种满足要求的粉刷方式？输出答案的最后5位即可。 【输入格式】 第一行两个数n, m，表示木板的长度，和指定规则的条目个数。 接下来m行，每行四个数x1,y1,x2,y1，此规则表示A(x1, y1) 需要等于 A(x2, y2) 。 【输出格式】 一个整数，表示答案的末5位。 【输入样例1】 1 0 【输出样例1】 67296 【输入样例2】 1 3 1 1 2 1 1 1 3 1 4 1 3 1 【输出样例2】 00256 【提示】 输出可以使用d输出。 【数据规模】 30% 数据满足 n ≤ 3，m = 0。 100% 数据满足1 ≤ n ≤ 15，0 ≤ M ≤ 100，X1,X2≤4，Y1,Y2≤n 【解法】 30分的做法：dp[i][c1][c2][c3]表示第i行，第一列填到c1，第二列填到c2,，第三列填到c3的方法总数。转移时如果暴力枚举转移仍然会TLE，需要使用完全背包的降低维度思想，列出转移方程：dp[i][c1][c2][c3]= dp[i-1][c1][c2][c3] + dp[i] [c1-1][c2][c3] + dp[i] [c1][c2-1][c3] + dp[i][c1][c2][c3-1]。这样才不会TLE。 100分的做法：换一种dp思路，我们不按照常规思维枚举行列，而是从小到大枚举颜色。若当前枚举到的颜色为i，我们使用dp[l1][l2][l3][l4]表示每一行使用当前颜色涂到哪一个位置。 假设有一行现在是123344556，现在涂7，显然涂7只能涂序列的后缀，比如涂成123777777，或者123344577才能符合条件。所以考虑枚举当前颜色涂到哪个后缀来转移，转移时同样需要使用完全背包的降维思想优化。 对于限制条件，我们需要把不符合限制条件的去掉，什么样的方案符合限制条件呢？对于限制条件A(x1, y1) = A(x2, y2)，和当前枚举到的颜色i，要么x1行和x2行，当前颜色都涂到了y1,y2位置，要么都没有涂到y1,y2位置。除此之外的都是不合法的方案，我们事先处理好一个vis数组，vis[l1][l2][l3][l4]表示四行分别涂到l1,l2,l3,l4，是否可行，在dp时如果遇到标记不可行的vis，这dp值设为0即可。
#include<iostream> #include<cstdio> #define LL long long #define clr(x) memset(x,0,sizeof(x)) #define ms(a,x) memset(x,a,sizeof(x)) using namespace std; const int MOD = 100000; const int maxn = 20; int n,m; int dp[maxn][maxn][maxn][maxn]; int vis[maxn][maxn][maxn][maxn]; int x1[105],x2[105],y1[105],y2[105]; int c[4]; template <class T> inline void read(T &x) { int flag = 1; x = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); } x *= flag; } int main() { // freopen("draw.in","r",stdin); // freopen("draw.out","w",stdout); read(n); read(m); for(int i = 1; i <= m; i++) read(x1[i]), read(y1[i]), read(x2[i]), read(y2[i]); for(int i = 1; i <= m; i++) for(c[0] = 0; c[0] <= n; c[0]++) for(c[1] = 0; c[1] <= n; c[1]++) for(c[2] = 0; c[2] <= n; c[2]++) for(c[3] = 0; c[3] <= n; c[3]++) if(c[x1[i]] >= y1[i] ^ c[x2[i]] >= y2[i]) vis[c[0]][c[1]][c[2]][c[3]] = 1; dp[1][1][1][1] = 1; for(int i = 1; i <= 255; i++) { for(int j = 1; j <= 4; j++) for(int k = 0; k <= n; k++) for(int t = 0; t <= n; t++) for(int l = 0; l <= n; l++) for(int x = 0; x <= n; x++) if(c[i] < n) { int tmp = dp[k][t][l][x]; c[i]++; dp[k][t][l][x] += tmp; dp[k][t][l][x] %= MOD; c[i]--; } for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) for(int t = 0; t <= n; t++) for(int l = 0; l <= n; l++) if(vis[j][k][t][l]) dp[j][k][t][l] = 0; } printf("d\n",dp[n][n][n][n]); return 0; }