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 阅读(266)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc