0x52 背包

数字组合

题意

从 $N$ 个正整数中选出若干数，和为 $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$ 拆成若干整数相加的形式。不考虑加数的顺序。至少拆成两个整数

解析：

完全背包。

令 fi,jf_{i,j}fi,j​ 为使用前 $i$ 个数将 $j$ 拆分的方案数，且没有拆成两个数的限制。

因为一个数必须拆成至少两个加数，所以不能将 $j$ 拆成 $j$。所以答案为 fn−1,nf_{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$ 个人，每个人有两个参数 pi,dip_i,d_ipi​,di​。从中选出 $m$ 个人，使 $|D-P|$ 最小，$D$ 为选出来的人的 did_idi​ 和，$P$ 同理。如果方案不唯一，选择 $D+P$ 最大的方案。

解析：

令 fi,j,kf_{i,j,k}fi,j,k​ 为在前 $i$ 人，选出 $j$ 人，$D-P=k$ 的最大的 $D+P$

$k$ 有可能是负数，加上偏移量 $base=400$

如果不选第 $i$ 个人: fi,j,k=fi−1,j,kf_{i,j,k} = f_{i-1, j, k}fi,j,k​=fi−1,j,k​

如果选第 $i$ 个人: fi,j,k=fi−1,j−1,k−di+pi+di+pif_{i,j,k} = f_{i-1, j-1, k-d_i+p_i}+d_i+p_ifi,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;elsev = 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$ 种硬币，其中第 $i$ 种硬币的面值为 AiA_iAi​，共有 CiC_iCi​ 个。

从中选出若干个硬币，把面值相加，若结果为 $S$，则称“面值 $S$ 能被拼成”。

求 $1\sim M$ 之间能被拼成的面值有多少个。

解析：

多重背包。

二进制拆分，将每种物品拆成 20,21,...2^0,2^1,...20,21,... 个，然后01背包。

时间复杂度为 $O(nmlogc)$，没法通过此题。

正解应为单调队列优化。大致思路是：将体积按照对 AiA_iAi​ 的余数分组，组之间互不影响。在同一组内部，维护一个价值递增的单调队列。用单调队列优化dp的转移。（因为比他set过了，就没写单调队列）

但对于此题，二进制拆分过不了，可以用bitset优化一下就过了。

代码：

#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;
}