#include <iostream>
using namespace std;
const int N = 110;
int t, n;
int v[N], w[N];
int f[N][N * 10];
int main() {
cin >> t >> n;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= t; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][t] << endl;
return 0;
}
活动打卡代码
AcWing 423. 采药
用快速幂算出n个人的所有方案数, 为2^n, 再用0-1背包的思想求出所有能力值小于k的方案数
二者之差就是最终答案
计蒜客上的一道题, 思考了很久终于想到一个解决方案 题目
题目描述
蒜头君作为蒜厂篮球队的经理，要从 n 名队员中选出若干人组队参加篮球争霸赛。为了获得参赛资格，球队中所有队员的能力值 p 之和不得小于 k。
现在给出你所有球员的能力值，请问蒜头君共有多少种组队方案。这个方案数可能很大，需要对 10007 取模。每个组队方案的人数没有任何限制。
输入格式
输入为 2 行：
第一行是两个空格隔开的整数 n, k (1 <= n <= 100, 1 <= k <= 10^4)
分别表示队员的数目和球队总能力值的下限；
第二行是 n 个空格隔开的整数 p (1 <= p <= 100)为每个球员的能力值；
输出格式
输出为 1 个整数，为蒜头君的组队方案数，结果对 10007 取模。
样例
样例输入
5 10
2 4 6 8 10
样例输出
25
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, K = 10010, MOD = 10007;
int n, k;
int p[N];
int f[N][K];
int qmi(int a, int b) {
int res = 1 % MOD;
while (b) {
if (b & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 0; i <= k - 1; i++) f[0][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k - 1; j++) {
f[i][j] = f[i - 1][j];
if (j >= p[i])
f[i][j] = (f[i][j] + f[i - 1][j - p[i]]) % MOD;
}
}
cout << (qmi(2, n) - f[n][k - 1] + MOD) % MOD << endl;
return 0;
}
用递归法逐个填充
从样例中可以看到，n 矩阵就是在 n - 1 矩阵的上面多一行 1~n，左侧多一列 1~n
由此可以用递归法来填充，先以坐标(1, 1)为起点填充 n 所在的一行一列，再把
横纵坐标都加1，递归填充 n - 1 所在的一行一列，一直到 n 等于 0 的时候结束。
#include <iostream>
using namespace std;
const int N = 110;
int n;
int a[N][N];
void ff(int n, int x, int y) {
if (n <= 0) return;
for (int i = 1; i <= n; i++) a[x][y + i - 1] = i, a[x + i - 1][y] = i;
ff(n - 1, x + 1, y + 1);
}
void print(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
}
cout << endl;
}
}
int main() {
while (1) {
cin >> n;
if (!n) break;
ff(n, 1, 1);
print(n);
cout << endl;
}
return 0;
}
分享
自动兑换机
自动兑换机
比赛时间到了没法验证了, 等待开放的时候再提交试试看.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m, t;
int a[N];
int f[110][N];
bool cmp(int a, int b) {
char x[20], y[20];
sprintf(x, "%d", a);
sprintf(y, "%d", b);
int i = 0, j = 0;
while (i < strlen(x) && j < strlen(y)) {
if (x[i] < y[j]) return false;
else if (x[i] > y[j]) return true;
i++, j++;
}
if (i == strlen(x)) return false;
return true;
}
int main() {
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
double c;
cin >> c;
m = c * 100;
sort(a + 1, a + 1 + n, cmp);
//for (int i = 1; i <= n; i++) cout << a[i] << ' ' ; cout << endl;
memset(f, 0x3f, sizeof(f));
for (int i = 0; i <= n; i++) f[i][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= a[i])
f[i][j] = min(f[i][j], f[i][j - a[i]] + 1);
}
}
int id = 0, rr = m;
for (int i = 1; i <= n; i++) {
//cout << f[i][m] << ' ';
if (f[i][m] <= rr) { id = i; rr = f[i][m]; }
}
if (id == 0) { cout << "No Solution" << endl; continue; }
cout << f[id][m] << ' ';
int i = id, j = m, all = m;
while (all > 0) {
int cnt = 0;
while (f[i][j] == f[i][j - a[i]] + 1) {
cnt++, all -= a[i], j -= a[i];
}
if (cnt) {
cout << a[i] << '*' << cnt;
if (all) cout << '+';
} else {
i--;
}
}
cout << endl;
}
return 0;
}
01背包问题，求体积恰好等于m时的最大价值
需要对 f 数组作特殊的初始化，详见代码注释。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
/* 当求体积正好等于 m 时的最大价值时，需要如下的初始化 */
// 1. 所有方案的价值都置为负无穷
memset(f, 0xf0, sizeof(f));
// 2. 只有当前体积为 0 时，对于所有物品 i，都有一种合法方案，就是
// 什么也不选，对应此时的最大价值为0.
// 3. 最后的答案还是 f[n][m]
for (int i = 0; i <= n; i++) f[i][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
BF 算法解决有边数限制的最短路径
为了防止链式更新, 需要用到一个 backup 数组, 以免 a 更新了 b, 在同一次迭代里 b 又更新了 c 点.
每次迭代都要枚举 m 条边有点笨, 所以 spfa 算法就是为了优化 BF 的, 用邻接表存储边, 每次只更新
d[a] 发生变化了的所有边. 用队列记录记录所有变化了的节点.
BF 算法也可以用来判断负环
迭代第 n 次时, 如果发现还有某个点的距离发生了变化, 那就说明存在一条长度为 n + 1 的路径, 就
必定存在负权回路.
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
struct Edge {
int a, b, c;
} edges[N];
int n, m, k, x, y, z;
int d[N], backup[N];
int bf() {
memset(d, 0x3f, sizeof(d));
d[1] = 0;
for (int i = 1; i <= k; i++) {
memcpy(backup, d, sizeof(d)); // 防止链式更新, 下面更新 d[b] 时要用到 backup[a] 不能用 d[a]
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, c = edges[j].c;
d[b] = min(d[b], backup[a] + c);
}
}
return d[n];
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
cin >> x >> y >> z;
edges[i].a = x, edges[i].b = y, edges[i].c = z;
}
int t = bf();
if (t > 0x3f3f3f3f / 2) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
活动打卡代码
AcWing 496. 机器翻译
这个提高组的题有点水
#include <iostream>
#include <queue>
#include <set>
using namespace std;
const int N = 1010, M = 110;
queue<int> q;
set<int> dict;
int n, m;
int ans;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (dict.count(x) == 0) {
ans++;
dict.insert(x), q.push(x);
if (q.size() > m) {
int t = q.front();
dict.erase(t), q.pop();
}
}
}
cout << ans << endl;
return 0;
}
活动打卡代码
AcWing 441. 数字统计
入门组的题越发的简单了起来....
#include <iostream>
using namespace std;
int l, r;
int ans;
int main() {
cin >> l >> r;
for (int i = l; i <= r; i++) {
int x = i;
while (x) {
if (x % 10 == 2) ans++;
x /= 10;
}
}
cout << ans << endl;
}
