uva4031 Integer Transmission (DP)題意:傳送一個長度在64之內的01串,第i時刻發送出第i字節(i=0,1,...,L-1).對任意第i時刻發出的字節,它有可能在i+1,i+2,...,i+d+1(d<=L)中的任一時刻到達接收端.當同一時刻有多個字節同時到達時,這些字節可以任意排列.問接收端可能收到多少種不同串? 并求出二進制最小的和最大的串.按位DP, 關鍵是確定前i位至多能有多少個0/1,至少必須有多少個0/1. 此題與windy's abc很相似, 但多了處變化.考慮 d=3, 原串為 1101011, 顯然第1個1永遠不可能跑到第2個0右邊. 字符串的錯位,本質上是某些1把它右邊d之內的0擠到左邊了. 因此對1, 它實際能向右移多少位,取決于它右邊d之內有多少個0.這樣預處理后按位DP即可.構造最小/最大數,只需盡量把1/0往低位扔就行了.代碼:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 #include <cmath>
7 using namespace std;
8
9 typedef unsigned long long ull;
10
11 int mi[2][130], mx[2][130];
12 ull dp[65][65];
13 int b[65];
14 int N,D;
15 ull K;
16 int CAS;
17
18 void init()
19 {
20 int i,j,k;
21 ull t;
22 memset(b,0,sizeof(b));
23 for(t=K, i=N; t; i--){
24 b[i] = t&1;
25 t>>=1;
26 }
27 int c[2][130];
28 memset(c,0,sizeof(c));
29 for(i=1; i<=N; i++)
30 c[b[i]][i]++;
31 for(i=N; i>=1; i--)
32 c[0][i] += c[0][i+1], c[1][i] += c[1][i+1];
33 memset(mi, 0, sizeof(mi));
34 memset(mx, 0, sizeof(mx));
35 for(i=1; i<=N; i++){
36 mx[b[i]][ min(N, i+c[b[i]^1][i+1]-c[b[i]^1][i+D+1]) ] ++;
37 }
38 for(i=N; i>=1; i--){
39 mx[0][i] += mx[0][i+1];
40 mx[1][i] += mx[1][i+1];
41 mi[0][i] = max(0, N+1-i-mx[1][i]);
42 mi[1][i] = max(0, N+1-i-mx[0][i]);
43 }
44 }
45
46 ull dodp()
47 {
48 int i,j,k,p;
49 ull ret = 0;
50 memset(dp,0,sizeof(dp));
51 for(i=0; i<=N; i++)
52 dp[N][i] = 1;
53 for(p=N; p>=1; p--){
54 for(i=mi[0][p]; i<=mx[0][p]; i++){
55 j=N+1-p-i;
56 if(j<mi[1][p] || j>mx[1][p]) continue;
57 if(dp[p][i]==0)continue;
58 if(p==1){ ret += dp[p][i]; continue; }
59 dp[p-1][i] += dp[p][i];
60 dp[p-1][i+1] += dp[p][i];
61 }
62 }
63 return ret;
64 }
65
66 void getans(ull &xx, ull &ii)
67 {
68 int i,j,k;
69 int c0[2][65],c1[2][65];
70 memset(c0,0,sizeof(c0));
71 memset(c1,0,sizeof(c1));
72 for(i=1; i<=N; i++){
73 if(b[i]==0)
74 c0[0][i]++, c1[0][min(N,i+D)]++;
75 else
76 c1[1][i]++, c0[1][min(N,i+D)]++;
77 }
78 //for(i=1; i<=N; i++
79 xx = ii = 0;
80 for(i=1; i<=N; i++){
81 while(c0[0][i]--) ii = (ii<<1);
82 while(c0[1][i]--) ii = (ii<<1)|1;
83
84 while(c1[1][i]--) xx = (xx<<1)|1;
85 while(c1[0][i]--) xx = (xx<<1);
86 }
87 }
88
89 void solve()
90 {
91 int i,j,k;
92 printf("Case %d: ", ++CAS);
93 printf("%llu ", dodp());
94 ull xx,ii;
95 getans(xx, ii);
96 printf("%llu %llu\n", ii, xx);
97 }
98
99 int main()
100 {
101 CAS = 0;
102 while(scanf("%d",&N)!=EOF && N){
103 scanf("%d %llu",&D,&K);
104 init();
105 solve();
106 }
107 }
108
posted on 2009-07-16 19:28
wolf5x 閱讀(288)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc