比赛链接

文章目录

题目描述


输入描述:

第一行一个数 n。 然后 n 行，每行两个数表示 li,ri。

输出描述:

输出一行一个数表示答案。

示例1
输入

5
1 2
2 3
3 4
4 5
5 6

输出

26

备注:
1 ≤ n , li , ri ≤ 100

题解：

xi的是在 [li , ri]中任选一个，然后构成值,所以可以用分组背包来做
dp[i][j]前i个数字能否构成j
那么dp [ i -1 ] [ j - x[ i ]* x [ i ] ] = = 1则说明加上第i个数则可以构成，x [ i ] 的取值范围 是题目所给 l[i]和r[i]
这样做肯定不行，哪那么简单
复杂度过高，我们需要压缩下
先注意dp的值无疑是0或1，所以可以用bitset.
bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。
这样，我们用dp [ i ]表示第i行的01串
dp [ i ]= dp [ i ] | ( d p [ i - 1 ] < < ( x [ j ] 2 ) )
bitset还有自带的求1的个数的count，这样就更方便了

代码：

#include<bits/stdc++.h>
#include<bitset>
using namespace std;
typedef long long ll; 
int num1,num2; 
const int maxn=130;
int a[maxn]; 
bitset<1000009>dp[130];
int n;
int main(){
    
  	cin>>n;
  	dp[0][0]=1;
  	for(int i=1;i<=n;i++)
  	{
   
  		int l,r;
  		cin>>l>>r;
  		for(int j=l;j<=r;j++)
  		dp[i]|=(dp[i-1]<<(j*j));
	}
	cout<<dp[n].count();
	return 0;
}