[UOJ 110][APIO2015]Bali Sculptures

danihao123 posted @ 2018年3月08日 19:42 in 题解 with tags UOJ APIO 动态规划 , 538 阅读
转载请注明出处:http://danihao123.is-programmer.com/

第一次做subtask题= =其实这题也没啥难度吧

其实就是两个subtask……

对于第一个subtask,就是满足\(1\leq n\leq 100\)且\(1\leq a\leq b\leq n\)。我们应该优先满足高位为\(0\),于是乎可以贪心,从高位枚举到低位,看是否能在满足之前几位的限制条件的同时满足这一位答案为\(0\)。这个判定过程的话,可以设计状态\(d[i][k]\)表示前\(i\)位割成\(k\)段是否满足约束条件,枚举断点\(O(n)\)转移。

第二个subtask,虽然有\(n\leq 2000\)但是满足\(a = 1\)。这意味着分段数想怎么小就怎么小,所以我们可以直接去求这个序列要满足限制条件的话最少可以割成几段,这样的话第二维就可以省掉了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 2005;
ll Y[maxn], S[maxn];
int n, a, b;
const int maxb = 41;
ll st = 0;
namespace Task1 {
  bool d[105][105];
  bool dp(int bi) {
    memset(d, 0, sizeof(d));
    d[0][0] = true;
    for(int i = 1; i <= n; i ++) {
      for(int k = 1; k <= b; k ++) {
        for(int j = 0; j < i; j ++) {
          ll sum = S[i] - S[j];
          if((sum & (st | (1LL << bi))) == 0LL) {
            d[i][k] = (d[i][k] || d[j][k - 1]);
          }
        }
      }
    }
    for(int k = a; k <= b; k ++) {
      if(d[n][k]) return true;
    }
    return false;
  }
};
namespace Task2 {
  int d[maxn];
  bool dp(int bi) {
    d[0] = 0;
    for(int i = 1; i <= n; i ++) {
      d[i] = 0x3f3f3f3f;
      for(int j = 0; j < i; j ++) {
        ll sum = S[i] - S[j];
        if(!(sum & (st | (1LL << bi)))) {
          d[i] = std::min(d[i], d[j] + 1);
        }
      }
    }
    return (d[n] <= b);
  }
};

ll solve() {
  ll ans = 0;
  for(int i = maxb; i >= 0; i --) {
    bool flag = n <= 100 ? Task1::dp(i) : Task2::dp(i);
    if(flag) {
      st |= (1LL << i);
    } else {
      ans |= (1LL << i);
    }
  }
  return ans;
}

int main() {
  scanf("%d%d%d", &n, &a, &b);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &Y[i]);
    S[i] = S[i - 1] + Y[i];
  }
  printf("%lld\n", solve());
  return 0;
}
JDC Result jessore 说:
Aug 31, 2022 02:46:18 PM

Jessore Divisional education board of Bangladesh has successfully conducted the Grade 8th terminal examination tests for both Junior School Certificate & Junior Dakhil Certificate course students at all districts under the division to the academic year of 2022, there are a huge number of students are appeared from all Secondary schools under the board like as previous years, JDC Result jessore and this is most important examination tests for class 8th standard students of the country.Government of Bangladesh, Secondary and Higher Secondary Education Board has successfully completed the JSC & JDC examinations in the month of November 2022 to all eligible students of the division at all selected examination centers at all rural and urban area schools, both of Junior School Certificate & Junior Dakhil Certificate terminal exams are conducted as per date sheet announced by all education board Bangladesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter