51nod 1201[整数划分] 1259[整数划分V2] 1597 [有限背包计数问题]

时间:2021-10-10 19:11:48

因为觉得这三题差不多,思路有相同的地方也有不同的地方,挺有趣的,所以放在一起。

51nod 1201整数划分:

题目大意:

给出n,将n分为1-n中若干个不同的数的和,求方案数,模一个被模烂的质数。(1<=n<=50000)

题解:

每个数不同,那么和最小的情况就是1,2,3…,
假设是1-i的和,那么就有 i(i+1)/2<=n,i<=2n
所以最多有 2n 个数。
于是可以dp。
fi,j,gi,j 分别表示现在已经有了i个不同的数,和为j,f表示方案数,g表示最小的数大于1的方案数。

转移显然有:
fi,j=[j>0]gi1,j1+[j>=i]fi,ji
gi,j=fi1,ji

所以转移可以简化为:
fi,j=[j>=i](fi1,ji+fi,ji)

时间复杂度: O(nn)

Code:

#include<cmath>
#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int mo = 1e9 + 7;

int n, m, ans, o, f[2][50001];

int main() {
scanf("%d", &n); m = sqrt(2.0 * n) + 1;
if(m > n) m = n;
f[0][0] = 1;
fo(i, 1, m) {
o = !o;
f[o][0] = 0;
int nn = i * (i - 1) / 2;
fo(j, 1, nn - 1) f[o][j] = 0;
fo(j, nn, n) f[o][j] = (f[o][j - i] + f[!o][j - i]) % mo;
ans = (ans + f[o][n]) % mo;
}
printf("%d", ans);
}

51nod 1259 整数划分V2:

题目大意:

给出n,将n分为1-n中若干个数的和,求方案数,模一个被模烂的质数。

题解:

这是我们发现数可以重复了,那么最多有n个数,于是刚才那个dp挂了。

但是它可以分块,设 m=n

对于前m个数,暴力无限背包,这一部分的复杂度是 O(nn)

对于第m+1个数到第n个数,发现最多用 n 个,所以有可以上之前的dp,转移更简单,因为不用考虑重复。

fi,j 表示现在已经有了i个数,和为j的方案数。

fi,j=[j>0]fi1,j1+[j>=i]fi,ji

时间复杂度: O(nn)

Code:

#include<cmath>
#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int mo = 1e9 + 7;

int n, m, o, ans, f[2][50001];

int main() {
scanf("%d", &n); m = sqrt(n * 1.0);
f[o][0] = 1;
fo(i, 1, m) {
o = !o;
fo(j, 0, i - 1) f[o][j] = f[!o][j];
fo(j, i, n) f[o][j] = (f[o][j - i] + f[!o][j]) % mo;
}
ans = f[o][n];
fo(i, 1, m) {
o = !o;
fo(j, 0, n) {
f[o][j] = 0;
if(j > m) f[o][j] = f[!o][j - (m + 1)];
if(j >= i) f[o][j] = (f[o][j] + f[o][j - i]) % mo;
}
ans = (ans + f[o][n]) % mo;
}
printf("%d", ans);
}

51nod 1597 有限背包计数问题

题目大意:

给出一个n,你有n种物品,第i种物品的体积为i,有i个,背包大小为n,求装满这个背包的方案数。

题解:

也是分块。
对于前 n 种物品,暴力多重背包。
对于第 n+1 种物品到第n种物品,直接用整数划分V2后面的dp即可。

时间复杂度: O(nn)

Code:

#include<cmath>
#include<cstdio>
#include<cstring>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
using namespace std;

const int N = 100005;

int n, m, o, f[2][N], g[2][N];

const int mo = 23333333;

int main() {
scanf("%d", &n); m = sqrt(n * 1.0);
f[o][0] = 1;
fo(i, 1, m) {
o = !o; memset(f[o], 0, sizeof(f[o]));
fo(j, 0, i - 1) {
int sum = 0;
fo(k, 0, (n - j) / i) {
sum += f[!o][k * i + j];
sum = (sum + mo) % mo;
f[o][k * i + j] = (f[o][k * i + j] + sum) % mo;
if(k >= i) sum -= f[!o][(k - i) * i + j];
}
}
}
int sum = f[o][n];
fo(i, 1, m) {
o = !o;
fo(j, 0, n) {
f[o][j] = 0;
if(j >= (m + 1)) f[o][j] = f[!o][j - (m + 1)];
if(j >= i) f[o][j] = (f[o][j] + f[o][j - i]) % mo;
}
sum = (sum + f[o][n]) % mo;
}
printf("%d", sum);
}