legoblock秀上限

很久没有做题了，前天做了一道题结果弱的一逼。。。搜了解题报告不说...还尼玛秀了上限

题意：

给出宽和高为n和m的一堵墙，手上有长为1,2,3,4高均为1的砖，问形成一个坚固的墙有多少种做法。

坚固的意思是，不能一刀切到底。

解法：

将问题进行分解。求的所有坚固的墙ans(w,h)=所有墙all(w,h)-所有不坚固的墙bro(w,h)

所有的墙all(w,h)=一层的所有情况x(w)**h

所有不坚固的墙bro(w,h) = ans(1,h)*all(w-1,h)+ans(2,h)*all(w-2,h)+...+ans(w-1,h)*all(1,h)

x(w,1) = x(w-1,1)+x(w-2,1)+x(w-3,1)+x(w-4,1)

显然剩下的就是dp了

细节：

因为取余数，做减法的时候，有可能会发生不够减的情况记得+R就好

自己犯的错误：

这题的范围是t <=100 n,m<=1000

如果对于每个case都进行dp的话，是n*n*t的复杂度

然后如果进行预处理的话是n*n*n

然后问题就出在这里了预处理的话会TLE

但是有个cheat的办法就是输入之后先判断下每个高度最大的w就能过。

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cstring>
 7 
 8 using namespace std;
 9 
10 const int MAXSIZE = 1005;
11 const int R = 1000000007;
12 int wall[MAXSIZE][MAXSIZE];
13 int ans[MAXSIZE][MAXSIZE];
14 int vw[MAXSIZE];
15 int vh[MAXSIZE];
16 int hm[MAXSIZE];
17 int t;
18 int wmax;
19 int hmax;
20 
21 
22 void input(){
23     cin>>t;
24     for ( int i = 0; i < t; i++ ) {
25         cin>>vh[i]>>vw[i];
26         wmax = wmax<vw[i] ? vw[i]:wmax;
27         hmax = hmax>vh[i] ? hmax:vh[i];
28     }
29     for ( int i = 0; i < t; i++ ) {
30         hm[vh[i]] = hm[vh[i]]>vw[i] ? hm[vh[i]]:vw[i];
31     }
32 }
33 
34 void init() {
35     memset(wall,0,sizeof(wall));
36     memset(ans,0,sizeof(ans));
37     wall[1][1] = 1;
38     wall[2][1] = 2;
39     wall[3][1] = 4;
40     wall[4][1] = 8;
41     ans[1][1] = 1;
42     ans[2][1] = 1;
43     ans[3][1] = 1;
44     ans[4][1] = 1;
45     for ( int w = 5; w <= wmax; w++ ) {
46         wall[w][1] = (wall[w][1] + wall[w-1][1]%R)%R;
47         wall[w][1] = (wall[w][1] + wall[w-2][1]%R)%R;
48         wall[w][1] = (wall[w][1] + wall[w-3][1]%R)%R;
49         wall[w][1] = (wall[w][1] + wall[w-4][1]%R)%R;
50     }
51     for ( int h = 1; h <= hmax; h++ ) {
52         wall[1][h] = 1;
53         ans[1][h] = 1;
54     }
55     for ( int w = 2; w <= wmax; w++ ) {
56         for ( int h = 2; h <= hmax; h++ ) {
57             wall[w][h] = ((long long)wall[w][h-1]*wall[w][1])%R;
58         }
59     }
60     for ( int h = 2; h <= hmax; h++ ) {
61         for ( int w = 2; w <= hm[h]; w++ ) {
62             long long t = 0;
63             for ( int k = 1; k < w; k++ ) {
64                 t += (long long)ans[k][h]*wall[w-k][h];
65                 t %= R;
66             }
67             ans[w][h] = wall[w][h] > t? wall[w][h]-t:wall[w][h]-t+R;
68             ans[w][h] %= R;
69         }
70     }
71 }
72 
73 void solve() {
74     for ( int i = 0; i < t; i++ ) {
75         cout<<ans[vw[i]][vh[i]]<<endl;
76     }
77 }
78 
79 
80 
81 int main() {
82     input();
83     init();
84     solve();
85     return 0;
86 }

sb一般的代码

最近老师安排的事情比较多，，，书看的也慢了。。。简直是弱爆了。。。