Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

Topcoder SRM 538 1050P

 1#include <iostream>
 2#include <vector>
 3#include <string>
 4using namespace std;
 5
 6#define madd(a,b) a=(a+b)%MOD
 7
 8const int MOD=1000000007;
 9const int MAXC=55, MAXH=75, MAXW=10, MAXB=15;
10long g[MAXC], Comb[MAXC][MAXC];
11int dp[MAXW][MAXB][MAXC][MAXH][MAXW][2];
12
13class SkewedPerspective
14{
15
16public:
17    int countThem(vector <int> cubes, int B, int w)
18    {
19        int n=cubes.size(), total=0;
20        int i, j, k;
21        for(i=0; i<n; i++) total+=cubes[i];
22        
23        for(i=0; i<=total; i++)
24            for(j=0; j<=i; j++)
25                Comb[i][j]=(j?(Comb[i-1][j]+Comb[i-1][j-1])%MOD:1);
26        g[0]=1;
27        for(i=0; i<n; i++)
28            for(j=total; j; j--)
29                for(k=1; k<=&& k<=cubes[i]; k++)
30                    g[j]=(g[j]+g[j-k]*Comb[j][k])%MOD;
31
32        long ans=0;
33        dp[1][0][0][0][0][0]=1;
34        for(int tower=1; tower<=w; tower++)for(int black=0; black<=B; black++)
35        for(int color=0; color<=total; color++)for(int need=0; need<=total+black*2; need++)
36        for(int needOdd=0; needOdd<=tower; needOdd++)for(int lastBlack=0; lastBlack<2; lastBlack++)
37        {
38            int x=dp[tower][black][color][need][needOdd][lastBlack];
39            if(!x)continue;
40            //get result
41            if(black+color>0 && (B-black)*2+total-color>=need && total-color>=needOdd)
42                ans=(ans+g[color]*x)%MOD;
43            //put colored
44            madd(dp[tower][black][color+1][need][needOdd][0], x);
45            if(lastBlack) continue;
46            //put black
47            int layer=black*2+color-(tower-1);
48            for(int blackSize=1; blackSize+black*2<=B*2; blackSize++)
49                if(blackSize%2==0)
50                    madd(dp[tower][black+blackSize/2][color][need][needOdd][1], x);
51                else
52                {
53                    if(!layer && blackSize==1continue;  //"b1bbbb"
54                    int needNow=(layer?layer-1:layer+1);
55                    if(need+needNow<=total+B*2)
56                        madd(dp[tower+1][black+(blackSize+1)/2][color][need+needNow][needOdd+needNow%2][1], x);
57                }

58
59        }

60        return int(ans);
61    }

62}
;
63
64int main()
65{
66    SkewedPerspective a;
67    int cubes[]={110};
68    vector<int> t(cubes, cubes+3);
69
70    cout<<a.countThem(t, 12)<<endl;
71    return 0;
72}

73

posted on 2012-04-09 17:30 Drolca 阅读(124) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理