SPOJ AEROLITE

题目链接: http://www.spoj.com/problems/AEROLITE/en/

--------------------------------------------------------------------------------------

虽然没有明确的区间,但做法还是和区间$DP$一样, 将左右两个区间合并成一个大区间

为了防止重复统计,每次左区间必须是有一个括号括在最外层的

自己做的方法的复杂度可达 $O((L1L2L3D)^2)$ 加上少量剪枝后仍有$3s$

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int mod = ;

 long long f[][][][];

 long long dfs(int l1, int l2, int l3, int d)

 {

     if(f[l1][l2][l3][d] != -)

         return f[l1][l2][l3][d];

     if(l1 + l2 + l3 == )

         return f[l1][l2][l3][d] = (d == );

     if(l1 + l2 + l3 < d)

         return f[l1][l2][l3][d] = ;

     f[l1][l2][l3][d] = ;

     for(int b1 = ; b1 <= l1; ++ b1)

         for(int b2 = ; b2 <= l2; ++ b2)

             for(int b3 = ; b3 <= l3; ++ b3)

                 {

                     if(b1 + b2 + b3 == )

                         continue;

                     for(int d1 = ; d1 < d ; ++d1)

                     {

                         if(b1)

                             f[l1][l2][l3][d] += dfs(b1 - , b2, b3,

                              d1 - ) * dfs(l1 - b1, l2 - b2, l3 - b3, d);

                         else if(b2)

                             f[l1][l2][l3][d] += dfs(, b2 - , b3, d1 - )

                             * dfs(l1, l2 - b2, l3 - b3, d);

                         else

                             f[l1][l2][l3][d] += dfs(, , b3 - , d1 - )

                             * dfs(l1, l2, l3 - b3, d);

                     }

                     for(int d2 = ; d2 <= d; ++d2)

                     {

                         if(b1)

                             f[l1][l2][l3][d] += dfs(b1 - , b2, b3,

                              d - ) * dfs(l1 - b1, l2 - b2, l3 - b3, d2);

                         else if(b2)

                             f[l1][l2][l3][d] += dfs(, b2 - , b3, d - )

                             * dfs(l1, l2 - b2, l3 - b3, d2);

                         else

                             f[l1][l2][l3][d] += dfs(, , b3 - , d - )

                             * dfs(l1, l2, l3 - b3, d2);

                     }

                 }

     return f[l1][l2][l3][d] %= mod;

 }

 int main()

 {

     int l1, l2, l3, d;

     for(int ca = ; ca <= ; ++ca)

     {

         memset(f, -, sizeof f);

         scanf("%d%d%d%d", &l1, &l2, &l3, &d);

         printf("%lld\n", dfs(l1, l2, l3, d));

     }

     return ;

 }

巴特西

SPOJ AEROLITE

最新文章

热门文章