0x52 背包
数字组合
题意
从 N N N 个正整数中选出若干数,和为 M M M,询问方案数
解析:
01背包。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int n, m;
int f[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
f[0] = 1;
for(int i = 1, v; i <= n; i++){
cin >> v;
for(int j = m; j >= v; j--)
f[j] += f[j-v];
}
cout << f[m];
return 0;
}
自然数拆分
题意:
给定一个数 N N N,将 N N N 拆成若干整数相加的形式。不考虑加数的顺序。至少拆成两个整数
解析:
完全背包。
令 f i , j f_{i,j} fi,j 为使用前 i i i 个数将 j j j 拆分的方案数,且没有拆成两个数的限制。
因为一个数必须拆成至少两个加数,所以不能将 j j j 拆成 j j j。所以答案为 f n − 1 , n f_{n-1,n} fn−1,n。
滚掉一维。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll mod = 2147483648;
typedef pair<int, int> pii;
ll f[maxn];
int n;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
f[0] = 1;
for(int i = 1; i < n; i++){
for(int j = i; j <= n; j++)
f[j] = (f[j]+f[j-i]) % mod;
}
cout << f[n] << endl;
return 0;
}
陪审团
题意:
n n n 个人,每个人有两个参数 p i , d i p_i,d_i pi,di。从中选出 m m m 个人,使 ∣ D − P ∣ |D-P| ∣D−P∣ 最小, D D D 为选出来的人的 d i d_i di 和, P P P 同理。如果方案不唯一,选择 D + P D+P D+P 最大的方案。
解析:
令 f i , j , k f_{i,j,k} fi,j,k 为在前 i i i 人,选出 j j j 人, D − P = k D-P = k D−P=k 的最大的 D + P D+P D+P
k k k 有可能是负数,加上偏移量 b a s e = 400 base = 400 base=400
如果不选第 i i i 个人: f i , j , k = f i − 1 , j , k f_{i,j,k} = f_{i-1, j, k} fi,j,k=fi−1,j,k
如果选第 i i i 个人: f i , j , k = f i − 1 , j − 1 , k − d i + p i + d i + p i f_{i,j,k} = f_{i-1, j-1, k-d_i+p_i}+d_i+p_i fi,j,k=fi−1,j−1,k−di+pi+di+pi
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e2+10;
const int maxm = 8e2+10;
const int base = 400;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int n, m;
int f[maxn][25][maxm];
int a[maxn], b[maxn];
int main(){
int T = 1;
vector<int> res;
while(1){
res.clear();
scanf("%d %d", &n, &m);
if(n == m && n == 0)
break;
memset(f, -INF, sizeof(f));
for(int i = 1; i <= n; i++)
scanf("%d %d", &a[i], &b[i]);
//for(int i = 0; i <= m; i++)
f[0][0][base] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
for(int k = 0; k <= base * 2; k++){
f[i][j][k] = f[i-1][j][k];
if(j == 0)
continue;
int c = k - a[i] + b[i];
if(c < 0 || c > 800)
continue;
f[i][j][k] = max(f[i][j][k], f[i-1][j-1][c] + a[i] + b[i]);
}
}
}
int v = 0;
while(f[n][m][base-v] < 0 && f[n][m][base+v] < 0)
v++;
if(f[n][m][base-v] > f[n][m][base+v])
v = base-v;
else
v = base+v;
int x = n, y = m;
int sump = 0, sumd = 0;
while(y){
if(f[x][y][v] == f[x-1][y][v])
x--;
else{
res.push_back(x);
v -= (a[x]-b[x]);
x--, y--;
}
}
for(int i = 0; i < res.size(); i++){
sump += a[res[i]];
sumd += b[res[i]];
}
printf("Jury #%d\n", T++);
printf("Best jury has value %d for prosecution and value %d for defence:\n", sump, sumd);
sort(res.begin(), res.end());
for(int i = 0; i < res.size(); i++){
printf(" %d", res[i]);
}
putchar('\n');
putchar('\n');
}
return 0;
}
硬币
题意:
给定 N N N 种硬币,其中第 i i i 种硬币的面值为 A i A_i Ai,共有 C i C_i Ci 个。
从中选出若干个硬币,把面值相加,若结果为 S S S,则称“面值 S S S 能被拼成”。
求 1 ∼ M 1∼M 1∼M 之间能被拼成的面值有多少个。
解析:
多重背包。
二进制拆分,将每种物品拆成 2 0 , 2 1 , . . . 2^0,2^1,... 20,21,... 个,然后01背包。
时间复杂度为 O ( n m l o g c ) O(nmlogc) O(nmlogc),没法通过此题。
正解应为单调队列优化。大致思路是:将体积按照对 A i A_i Ai 的余数分组,组之间互不影响。在同一组内部,维护一个价值递增的单调队列。用单调队列优化dp的转移。(因为比他set过了,就没写单调队列)文章来源:https://www.toymoban.com/news/detail-414865.html
但对于此题,二进制拆分过不了,可以用bitset优化一下就过了。文章来源地址https://www.toymoban.com/news/detail-414865.html
代码:
#include<iostream>
#include<bitset>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e2+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int a[maxn], c[maxn], w[maxm], tot;
int n, m;
bitset<maxm> f;
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while(1){
cin >> n >> m;
if(n == 0 && m == 0)
break;
f.reset();
tot = 0;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> c[i];
for(int i = 1; i <= n; i++){
int tmp = a[i];
int cnt = 0, curw = 1;
while(cnt + curw <= c[i]){
w[++tot] = a[i];
cnt += curw;
curw <<= 1;
a[i] <<= 1;
}
c[i] -= cnt;
if(c[i])
w[++tot] = tmp * c[i];
}
f[0] = 1;
for(int i = 1; i <= tot; i++){
f = f | (f << w[i]);
}
int res = 0;
for(int i = 1; i <= m; i++)
res += f[i];
cout << res << endl;
}
return 0;
}
到了这里,关于《算法竞赛进阶指南》0x52 背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!