企业网上书店网站建设设计,高端企业网站设计公司,那个平台能免费做网站,优秀网站的颜色搭配比赛链接 文章目录题目描述题解#xff1a;代码#xff1a;题目描述 输入描述: 第一行一个数 n。 然后 n 行#xff0c;每行两个数表示 li,ri。 输出描述: 输出一行一个数表示答案。 示例1 输入
5
1 2
2 3
3 4
4 5
5 6输出
26备注: 1 ≤ n , li , ri ≤ 100
题解#xf…比赛链接
文章目录题目描述题解代码题目描述 输入描述: 第一行一个数 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这样就更方便了
代码
#includebits/stdc.h
#includebitset
using namespace std;
typedef long long ll;
int num1,num2;
const int maxn130;
int a[maxn];
bitset1000009dp[130];
int n;
int main(){ cinn;dp[0][0]1;for(int i1;in;i){int l,r;cinlr;for(int jl;jr;j)dp[i]|(dp[i-1](j*j));}coutdp[n].count();return 0;
}
