题目链接: http://www.spoj.com/problems/AEROLITE/en/
--------------------------------------------------------------------------------------
虽然没有明确的区间,但做法还是和区间$DP$一样, 将左右两个区间合并成一个大区间
为了防止重复统计,每次左区间必须是有一个括号括在最外层的
自己做的方法的复杂度可达 $O((L1L2L3D)^2)$ 加上少量剪枝后仍有$3s$
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 const int mod = 11380; 7 long long f[12][12][12][32]; 8 long long dfs(int l1, int l2, int l3, int d) 9 { 10 if(f[l1][l2][l3][d] != -1) 11 return f[l1][l2][l3][d]; 12 if(l1 + l2 + l3 == 0) 13 return f[l1][l2][l3][d] = (d == 0); 14 if(l1 + l2 + l3 < d) 15 return f[l1][l2][l3][d] = 0; 16 f[l1][l2][l3][d] = 0; 17 for(int b1 = 0; b1 <= l1; ++ b1) 18 for(int b2 = 0; b2 <= l2; ++ b2) 19 for(int b3 = 0; b3 <= l3; ++ b3) 20 { 21 if(b1 + b2 + b3 == 0) 22 continue; 23 for(int d1 = 1; d1 < d ; ++d1) 24 { 25 if(b1) 26 f[l1][l2][l3][d] += dfs(b1 - 1, b2, b3, 27 d1 - 1) * dfs(l1 - b1, l2 - b2, l3 - b3, d); 28 else if(b2) 29 f[l1][l2][l3][d] += dfs(0, b2 - 1, b3, d1 - 1) 30 * dfs(l1, l2 - b2, l3 - b3, d); 31 else 32 f[l1][l2][l3][d] += dfs(0, 0, b3 - 1, d1 - 1) 33 * dfs(l1, l2, l3 - b3, d); 34 } 35 for(int d2 = 0; d2 <= d; ++d2) 36 { 37 if(b1) 38 f[l1][l2][l3][d] += dfs(b1 - 1, b2, b3, 39 d - 1) * dfs(l1 - b1, l2 - b2, l3 - b3, d2); 40 else if(b2) 41 f[l1][l2][l3][d] += dfs(0, b2 - 1, b3, d - 1) 42 * dfs(l1, l2 - b2, l3 - b3, d2); 43 else 44 f[l1][l2][l3][d] += dfs(0, 0, b3 - 1, d - 1) 45 * dfs(l1, l2, l3 - b3, d2); 46 } 47 } 48 return f[l1][l2][l3][d] %= mod; 49 } 50 int main() 51 { 52 int l1, l2, l3, d; 53 for(int ca = 1; ca <= 10; ++ca) 54 { 55 memset(f, -1, sizeof f); 56 scanf("%d%d%d%d", &l1, &l2, &l3, &d); 57 printf("%lld ", dfs(l1, l2, l3, d)); 58 } 59 return 0; 60 }