uva1228 Integer Transmission

这道题思维很灵活。也有点套路的意思。

首先规定0,1分别按照原来的顺序接收，只是01换位。这样简化了思维。（否则并不会有更优结果它。，比较好想）
最大值和最小值可以贪心得到。
那么接下来就是给定一个整数P，判断能不能得到它。
贪心法，从左到右判断P的每一位，从K中最左边的0或1取。
这样会发现任意时刻k中已经被接收的位最右边那那位一定没有延迟（想一想，也比较好想）
设d(i，j)表示用了k的前i个0，前k个1后形成的整数数
则下一个接收的bit是0，转移d（i+1，j）
1 则d（i，j+1）
判断下一个接受的能否为1或0
设第i个0发送时间为Zi，对应有Oi，那么Oj+d>=Zi才可以转移到i+1；j+1对应画图证一下(用到上一个结论；比如i+1的情况，分接受的最后一位是0或1讨论；还要注意1用完了就不能这么判断了)
同时判断0,1有没有用完

这样就把十进制转化成二进制了
for(int i = 0; i < n; i++) {
K[n-i-1] = k % 2; k /= 2;
}

还要注意k，min，max要用ull

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = ;

int n, d, K[maxn];

long long f[maxn][maxn];

unsigned long long minv, maxv;  //ull ！！！

int zcnt = , ocnt = ;

int Z[maxn], O[maxn];

bool can_receive_zero(int i, int j) {

  return i+ <= zcnt && (j == ocnt || O[j]+d >= Z[i]);

}

bool can_receive_one(int i, int j) {

  return j+ <= ocnt && (i == zcnt || Z[i]+d >= O[j]);

}

void solve() {

  // compute Z and O

  ocnt = zcnt = ;

  for(int i = ; i < n; i++)

    if(K[i] == ) O[ocnt++] = i;

    else Z[zcnt++] = i;

  minv = maxv = ;

  int i = , j = ;

  while(i < zcnt || j < ocnt) {

    if(can_receive_zero(i, j))      //贪心策略0越前越好

        { i++; minv = minv * ; }

    else

        { j++; minv = minv *  + ; }

  }

  i = j = ;

  while(i < zcnt || j < ocnt) {

    if(can_receive_one(i, j)) { j++; maxv = maxv *  + ; }

    else { i++; maxv = maxv * ; }

  }

  // dp

  memset(f, , sizeof(f));

  f[][] = ;

  for(int i = ; i <= zcnt; i++)

    for(int j = ; j <= ocnt; j++) {

      if(can_receive_zero(i, j))

        f[i+][j] += f[i][j];

      if(can_receive_one(i, j))

        f[i][j+] += f[i][j];

    }

  cout << f[zcnt][ocnt] << " " << minv << " " << maxv << "\n";

}

int main() {

  int kase = ;

  unsigned long long k;

  while(cin >> n >> d >> k) {

    for(int i = ; i < n; i++) {

      K[n-i-] = k % ; k /= ;

    }

    cout << "Case " << ++kase << ": ";

    solve();

  }

  return ;

}

巴特西

uva1228 Integer Transmission

最新文章

热门文章