本文主要是介绍简单瞎搞题 (分组背包),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
简单瞎搞题
链接:https://ac.nowcoder.com/acm/contest/24213/1035
题目描述
一共有 n个数,第 i 个数是 xi
xi 可以取 [li , ri] 中任意的一个值。
设 S = ∑x i ^ 2 ,求 S 种类数。
输入描述:
第一行一个数 n。
然后 n 行,每行两个数表示 li,ri。
输出描述:
输出一行一个数表示答案。
示例1
输入
5
1 2
2 3
3 4
4 5
5 6
输出
26
备注:
1 ≤ n , li , ri ≤ 100
思路 :
令 dp[i][j]表示为第 i 次选择时,和为 j的情况是否出现过
但是内存方面需要 1e8 的 int 内存,显然是不可接受的
那么我们考虑用 bitset优化一下,有递推方程
代表第 i次选择的时候是否能从当前状态转移到和为 j的状态
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=105;
bitset<N>f[M];int main(){int n;cin >> n;f[0][0] = 1;for(int i = 1;i <= n;i ++){int l, r;cin >> l >> r;for(int j = l;j <= r;j ++){f[i] |= f[i - 1] << j * j;}}cout << f[n].count() << endl;return 0;
}
这篇关于简单瞎搞题 (分组背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!