1.
我们一个一个条件地分析：
1 要花光所有的钱：
首先，三种文具的价格是 3,4,73,4,7 ，通过证明，发现除了 n=1 ,n=2 , n=5 以外，任何的价格 n 都可以被花光，所以这个条件并没有什么太大的约束力；
2 尽量配成更多套
一套的价钱是 1414 元，所以这个规定就是要我们尽可能地买更多的整 1414 元；
3 尽量买更多的物品 ：
这个规定其实就是在我们买了尽可能多的整 14 元之后，剩余的钱再尽量拆分成 3 元或 44 元（因为 7=3+4 ，这样买的物品数量就会减少，所以不买 7 元的东西）
#include<cstdio> #include<iostream> using namespace std; int main() { int n; int a,b,c; scanf("%d",&n); a=n/14; b=n/14; c=n/14; if (n==1||n==2||n==5) { printf("-1"); return 0; } else if (n%14==1) { c--; b=b+2; } else if (n%14==2) { a=a+3; c--; } else if (n%14==3) { a++; } else if (n%14==4) { b++; } else if (n%14==5) { c--; a=a+4; } else if (n%14==6) { a=a+2; } else if (n%14==7) { a++; b++; } else if (n%14==8) { b=b+2; } else if (n%14==9) { a=a+3; } else if (n%14==10) { a=a+2; b=b+1; } else if (n%14==11) { a=a+1; b=b+2; } else if (n%14==12) { a=a+4; } else if (n%14==13) { a=a+3; b=b+1; } printf("%d %d %d",c,b,a); return 0; }
2.
把一个整数N拆分为K个数之和的问题
我们可以得知，递推公式为
f(n, k) = f(n-1, k-1) + f(n-k, k)
节约内存。想了想可以尝试使用滚动数组。要使用滚动数组，我需要调整动态规划的计算方向，之前是按行更新，需要调整成按列更新
#include <bits/stdc++.h> #define LL long long using namespace std; const int N = 100005; int f[N]; int g[400][N]; int main() { int n, p; cin >> n >> p; int m = sqrt(n) + 1; f[0] = 1; for (int i = 1; i < m; i++) { for (int j = i; j <= n; j++) { f[j] += f[j - i]; f[j] %= p; } } g[0][0] = 1; for (int i = 1; i < m; i++) { for (int j = i; j <= n; j++) { g[i][j] = g[i][j - i]; if (j >= m) g[i][j] += g[i - 1][j - m]; g[i][j] %= p; } } int ans = 0; for (int i = 0; i <= n; i++) { LL sum = 0; for (int j = 0; j < m; j++) sum += g[j][n - i]; sum %= p; ans = (ans + f[i] * sum) % p; } cout << ans << endl; return 0; }
3.
k=0
直接跑Floyd 即可得出结果（传送门：Floyd算法）
k=1
设 f k,i,j 表示在使用不超过 k次魔法的情况下，从 i 到 j 的最短路。
现在我们知道了 f 0,i,j,如何得到 f 1,i,j呢？
边的规模只有 2500，我们可以直接枚举要用魔法的边，转移时强制走这条边，求最短路。
假如边 (u,v,w)用了魔，
k=2
我们已经得到了k=1 的情况，如何推 k=2 的情况呢？
类似于 Floyd，我们可以枚举一个中转点 k，i→k 最多用一次魔法，k→j 最多用一次魔法，合并起来就是最多两次魔法的答案了。
这个可以用矩阵快速幂来优化转移,最多用 i 次魔法的结果和最多用 j次魔法的结果按照上面的转移方式合并的话，可以得到最多用 i+j 次魔法的结果
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF = 0x3f3f3f3f3f3f3f3f; const int N = 100; typedef LL Matrix[N][N]; int sz; LL a[N][N]; void matrix_mul(Matrix A, Matrix B, Matrix res) { Matrix C; for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { C[i][j] = INF; for (int k = 0; k < sz; k++) { C[i][j] = min(C[i][j], A[i][k] + B[k][j]); } } } for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { res[i][j] = C[i][j]; } } } void matrix_pow(Matrix A, LL p, Matrix res) { Matrix x; for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { x[i][j] = A[i][j]; res[i][j] = a[i][j]; } } while (p) { if (p & 1) matrix_mul(res, x, res); p >>= 1; matrix_mul(x, x, x); } } struct Edge { int u, v, w; } b[2505]; int main() { int n, m, K; scanf("%d%d%d", &n, &m, &K); sz = n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i][j] = i == j ? 0 : INF; for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); u--; v--; b[i] = {u, v, w}; a[u][v] = min(a[u][v], (LL)w); } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = min(a[i][j], a[i][k] + a[k][j]); } } } Matrix c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i][j] = a[i][j]; for (int k = 0; k < m; k++) { c[i][j] = min(c[i][j], a[i][b[k].u] - b[k].w + a[b[k].v][j]); } } } matrix_pow(c, K, c); printf("%lld ", c[0][n - 1]); return 0; }