【每日一题】简单瞎搞题

title: 每日一题：简单瞎搞题 （STL）
copyright: true
date: 2020-05-26 17:44:37
tags: STL
category: 每日一题
mathjax: true

题意

一共有 个数，第 个数是 可以取 中任意的一个值。设 ，求 种类数。（0 ~ n,l,r ~ 100）

Solution

表示前 个数能不能组成 ，可以得到转移方程：，最后统计 层组成的 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程：，复杂度 。

Code

#include <bits/stdc++.h>
using namespace std;
bitset<1000005> dp[105];
int main() {
  int n, l, r;
  scanf("%d", &n);
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &l, &r);
    for (int j = l; j <= r; j++) dp[i] |= dp[i - 1] << (j * j);
  }
  printf("%lu\n", dp[n].count());
  return 0;
}