一
T1:小奇挖矿2
因为只能走4步或7步,可以发现,当步数差\(\ge18\)时,一定能到达。而当步数差\(<18\)时,枚举出所有能到达的情况即可。
#include<bits/stdc++.h>
#define rg register
#define qwq 0
#define int long long
using namespace std;
const int N = 1e5 + 3;
int n, m;
struct node {
int a, b;
} c[N];
inline bool cmp(node x, node y) {
return x.b < y.b;
}
int dp[N], f[N];
bool vis[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (rg int i = 1; i <= n; i++) {
cin >> c[i].a >> c[i].b;
}
sort(c + 1, c + n + 1, cmp);
vis[0] = true;
rg int ans = 0;
for (rg int i = 1; i <= n; i++) {
for (rg int j = i; j >= 0; j--) {
if (c[i].b - c[j].b >= 18) {
dp[i] = max(dp[i], f[j] + c[i].a);
break;
}
if (vis[j]) {
if (c[i].b - c[j].b == 0) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 4) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 7) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 8) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 11) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 12) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 14) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 15) dp[i] = max(dp[i], dp[j] + c[i].a);
if (c[i].b - c[j].b == 16) dp[i] = max(dp[i], dp[j] + c[i].a);
}
}
if (dp[i] != 0) vis[i] = true;
f[i] = max(f[i - 1], dp[i]);
}
cout << f[n] << "\n";
return qwq;
}
T2:小奇的矩阵(matrix)
容易推出,\(V = (n+m-1)\times pfh-sum^2\),其中pfh为选的数的平方的和,sum为选的数的和。
令\(f[i][j][k]\)表示当前坐标\((i,j)\),总值为k的最小值。
#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 33;
int T, n, m;
int a[N][N];
int f[N][N][2005];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while (T--) {
memset(f, -1, sizeof(f));
cin >> n >> m;
rg int len = n + m - 1;
for (rg int i = 1; i <= n; i++) {
for (rg int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
f[1][1][a[1][1]] = a[1][1] * a[1][1];
for (rg int i = 1; i <= n; i++) {
for (rg int j = 1; j <= m; j++) {
for (rg int k = a[i][j]; k <= 1500; k++) {
if (i == 1 && j == 1) continue ;
if (f[i - 1][j][k - a[i][j]] != -1) {
f[i][j][k] = f[i - 1][j][k - a[i][j]] + a[i][j] * a[i][j];
}
if (f[i][j - 1][k - a[i][j]] != -1) {
if (f[i][j][k] == -1) f[i][j][k] = f[i][j - 1][k - a[i][j]] + a[i][j] * a[i][j];
else f[i][j][k] = min(f[i][j][k], f[i][j - 1][k - a[i][j]] + a[i][j] * a[i][j]);
}
}
}
}
rg int ans = 2e9;
for (rg int i = 0; i <= 1500; i++) {
if (f[n][m][i] == -1) continue ;
ans = min(ans, f[n][m][i] * len - i * i);
}
cout << ans << "\n";
}
return qwq;
}
T3:小奇的仓库(warehouse)
换根DP。
若\(M=0\)很简单,但异或M不好处理。观察到M最大为15,最多只会对一个数的最后四位造成影响,于是将最后四位单独处理。
令\(f[i]\)表示以i为根的子树内的节点到i的距离之和(减去后四位),\(siz[i]\)表示此时距离以j为后缀的共有几个。
每一次向根节点方向转移时会加上一条边的长度,此时不同距离的后缀会发生相应的改变,然后更新父亲相应后缀的siz值。
f中统计的距离总和是抹掉所有后缀后的总和,等到最后根节点统计答案时再考虑每个后缀的贡献。
还有一点,因为\(0 xor M\)值为M,因此最后答案要减去M。
#include<bits/stdc++.h>
#define rg register
#define qwq 0
using namespace std;
const int N = 1e5 + 3;
int siz[N][17], fn[N], f[N];
int n, m;
struct edge {
int to, val;
};
vector<edge> e[N];
inline void dfs1(int u, int fath) {
siz[u][0] = 1;
for (rg int i = 0; i < e[u].size(); i++) {
rg int v = e[u][i].to, w = e[u][i].val;
if (v == fath) continue ;
dfs1(v, u);
f[u] += f[v];
for (rg int j = 0; j <= 15; j++) {
rg int ret = j + w;
rg int res = ret & 15;
siz[u][res] += siz[v][j];
f[u] += siz[v][j] * (ret - res); //剔除后缀
}
}
}
int sizn[N][17];
inline void dfs2(int u, int fath) {
fn[u] = f[u];
for (rg int i = 0; i <= 15; i++) {
fn[u] += (i ^ m) * siz[u][i];
}
for (rg int i = 0; i <= 15; i++) {
sizn[u][i] = siz[u][i];
}
rg int bf = f[u];
for (rg int i = 0; i < e[u].size(); i++) {
rg int v = e[u][i].to, w = e[u][i].val;
if (v == fath) continue ;
rg int ret, res;
for (rg int j = 0; j <= 15; j++) {
ret = j + w;
res = ret & 15;
siz[u][res] -= siz[v][j];
f[u] -= siz[v][j] * (ret - res);
}
f[v] = f[u];
for (rg int j = 0; j <= 15; j++) {
ret = j + w;
res = ret & 15;
siz[v][res] += siz[u][j];
f[v] += siz[u][j] * (ret - res);
}
dfs2(v, u);
f[u] = bf;
for (rg int j = 0; j <= 15; j++) {
siz[u][j] = sizn[u][j];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (rg int i = 1; i < n; i++) {
rg int x, y, z;
cin >> x >> y >> z;
e[x].push_back({y, z});
e[y].push_back({x, z});
}
dfs1(1, 0);
dfs2(1, 0);
for (rg int i = 1; i <= n; i++) {
cout << fn[i] - m << "\n";
}
return qwq;
}
T4:[COCI2014-2015#1] Kamp
令\(siz[i]\)表示i子树内关键点数量,\(f[i]\)表示i子树内完成任务并回到i的花费,\(g[i]\)表示i子树外完成任务并回到i的花费,\(dis[i][0]\)表示i子树内的最长链,\(dis[i][1]\)表示i子树内的次长链,\(up[i]\)表示i子树内的最长链。
标签:总结,子树内,int,max,rg,模拟,dp,define From: https://www.cnblogs.com/Baiyj/p/18244509