ABC344 D-F
**D - String Bags **
标签
动态规划DP
思路
这一题可以想到使用\(DP\)。
那么\(f[i][j]\)就表示在前\(i\)个包里选择长度为\(j\)的字符串最小钱数。这里的字符串时字符串\(T\)的子串
那么状态转移方程就是
f[i + 1][j + s.size()] = min(f[i + 1][j + s.size()], f[i][j] + 1);
这里的\(j\)是逆序枚举字符串s。它的意思是说在选择和不选择中选一个取最小值
代码
#include<bits/stdc++.h>
using namespace std;
int f[105][105];
int main() {
string t;cin >> t;
int n = t.size();
t = " " + t;
int q;scanf("%d", &q);
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < q; i++) {
for (int j = 0; j <= n; j++) f[i + 1][j] = f[i][j];
int k;scanf("%d", &k);
while (k--) {
string s;cin >> s;
for (int j = n - (int)s.size(); j >= 0; j--) {
if (t.substr(j + 1, s.size()) == s) f[i + 1][j + s.size()] = min(f[i + 1][j + s.size()], f[i][j] + 1);
}
}
}
if (f[q][n] == 0x3f3f3f3f)puts("-1");
else printf("%d", f[q][n]);
}
E - Insert or Erase
标签
链表，模拟
思路
首先我们先模拟以先一个链表\(\{1,5,4,2,3\}\)
如果我们要删除或增加一个数，那么我们必须知道这一个数的位置，所以我们可以用一个map来存储每一个数的位置。
现在我们要删除一个数\(4\),那么这个链表就会是\(\{1,5,2,3\}\)
那我们只用把到\(4\)的边连接到\(4\)的下一个点，把另一个方向的边连接到\(4\)的上一个点即可
那如果要在\(1\)后面插入一个\(6\)那链表就会变成\(\{1,6,5,2,3\}\)
所以说这一题就是直接模拟一下上面的过程即可。
代码
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val, l, r;
} node[400005];
int head = 0;
map<int, int> node_id;
int node_cnt = 0;
int newnode(int x) {
if (node_id.count(x)) {
return node_id[x];
} else {
node[node_cnt].val = x;
node[node_cnt].l = node[node_cnt].r = -1;
node_id[x] = node_cnt;
return node_cnt++;
}
}
void link(int a, int b) {
node[a].r = b;
node[b].l = a;
}
void insert(int a, int b) {
int c = node[a].r;
link(a, b);
if (c != -1) link(b, c);
}
void remove(int x) {
int a = node[x].l, b = node[x].r;
if (a == -1) {
assert(x == head);
head = node[x].r;
node[b].l = node[x].r = -1;
}
else if (b == -1)node[a].r = node[x].l = -1;
else {
link(a, b);
node[x].l = node[x].r = -1;
}
}
int main() {
int n;scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;scanf("%d", &x);
int id = newnode(x);
if (i) link(i - 1, id);
}
int q;scanf("%d", &q);
while (q--) {
int tp;scanf("%d", &tp);
if (tp == 1) {
int x, y;scanf("%d %d", &x, &y);
insert(node_id[x], newnode(y));
}
else {
int x;scanf("%d", &x);
remove(node_id[x]);
}
}
int now = head;
while (now != -1) {
printf("%d ", node[now].val);
now = node[now].r;
}
return 0;
}
F - Earn to Advance
标签
动态规划DP
思路
在不改变答案的情况下，可以将第一个操作 "增加资金\(P_{i,j}\)"改为 "增加迄今为止通过的单元格中最大的\(P_{i,j}\)"。
因此，我们可以假设他只在需要时才赚钱；这样，一旦路径固定下来，最优方案也就确定了。
\(f[i][j][u][v]\)就可以表示成在\(C\)单元格时的最大值(金钱)，以及目前单元格中最大值\(P_{i,j}\)
这个\(DP\)有\(O(N^4)\)个状态，转换花费\(O(1)\)个时间，因此总共需要\(O(N^4)\)个时间来求解。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 85;
int p[N][N], r[N][N], d[N][N];
LL f[N][N], g[N][N], h[N][N][N][N];
int main() {
int n;scanf("%d", &n);
for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)scanf("%d", &p[i][j]);
for (int i = 1; i <= n; i++)for (int j = 1; j < n; j++)scanf("%d", &r[i][j]);
for (int i = 1; i < n; i++)for (int j = 1; j <= n; j++)scanf("%d", &d[i][j]);
memset(h, 0x3f, sizeof(h));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
h[i][j][i][j] = 0;
for (int u = i; u <= n; u++) {
for (int v = j; v <= n; v++) {
if (u == i && v == j) continue;
h[i][j][u][v] = min(h[i][j][u - 1][v] + d[u - 1][v], h[i][j][u][v - 1] + r[u][v - 1]);
}
}
}
memset(f, 0x3f, sizeof(f));
f[1][1] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int u = 1; u <= i; u++)
for (int v = 1; v <= j; v++) {
LL c = (max(0ll, h[u][v][i][j] - g[u][v]) + p[u][v] - 1) / p[u][v];
if (f[i][j] > f[u][v] + c + i - u + j - v) {
f[i][j] = f[u][v] + c + i - u + j - v;
g[i][j] = g[u][v] + p[u][v] * c - h[u][v][i][j];
}
else if (f[i][j] == f[u][v] + c + i - u + j - v)
g[i][j] = max(g[i][j], g[u][v] + p[u][v] * c - h[u][v][i][j]);
}
printf("%lld", f[n][n]);
return 0;
}