2023年10月1日
今天是DP!加油吧哎，接受自己的菜，也得接受之前造成的影响可恶啊。
Awcing282 石子合并
题目大意
把相邻的石子，进行合并，花费是两堆石子的数量和。问把所有石子合并成一堆的最小花费。
题目理解
- yxcDP分析大法
- 是经典的区间 DP
- 因为只能合并相邻的便是
Dp问题 - 我们把
f[i][j]看作合并从[i, j]为一堆的集合 - 属性便是个数
切记！区间DP的枚举方式。
代码实现
/*
y式dp分析法：化0为整的过程
状态表示：
集合：所有将 [i, j] 合并成一堆的方案的集合
属性：每一个方案的最小值
状态转化：
因为：f[i][j] 代表把从[i, j] 合并成一堆的方案集合那么
f[i][j] = min(f[i][j], f[i - 1][k] + f[k + 1][j])
k 是从 i 一直到 j - 1
*/
const int N = 310;
int w[N];
int d[N][N];
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)cin >> w[i], w[i] += w[i - 1];
// 一般都是枚举区间长度
for(int len = 2; len <= n; len++)
for(int i = 1; i + len - 1 <= n; i++) // 枚举左端点
{
// 枚举右端点
int j = i + len - 1;
d[i][j] = INF;
for(int k = i; k <= j - 1; k++)
d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + w[j] - w[i - 1]);
}
cout << d[1][n];
return;
}
Acwing900 整数划分
题目理解
一步步分析出来了！
/*
f[i][j] 表示，用前i个数，组合成j的方法数
状态表示：
集合： 1 ~ i 能组合成数字j的集合
属性： cnt方案数
状态转移：
f[i][j] = f[i - 1][j] + ()
f[i - 1][j] 是1 ~ i减一组合成`j`的方法
如果我选了j这个数，f[i][j]
i是可以选择 [0, j / i]个
f[i][j] = sum(f[i - 1][j], f[i - 1][j - 1 * i], f[i - 1][j - 2 * i], ... f[i - 1][j - k * i])
f[i][j - i] = sum(f[i - 1][j - i], f[i - 1][j - 2 * i], f[i - 1][j - 3 * i], ...)
f[i][j] = f[i - 1][j] + f[i][j - i];
最后的答案就是f[n][n]
*/
代码实现
const int N = 1010;
int d[N][N];
void solve()
{
int n;
cin >> n;
for(int i = 0; i <= n; i++) d[i][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= n; j++)
{
d[i][j] = d[i - 1][j];
if(j >= i)
d[i][j] = (d[i - 1][j] + d[i][j - i]) % Mod;
}
cout << d[n][n];
return;
}
Acwing5268 Python缩进
题目理解
/*
ysdp分析法
f[i][j] 表示第i条语句缩进了j级组成的方案数
如果前面一句是f: f[i][j] = f[i - 1][j - 1]
如果前面一句是S:
f[i][j] = f[i - 1][j] + f[i][0] + f[i][1] + ... f[i][j - 1];
f[i][j + 1] = f[i][0] + ... + f[i][j]
*/
代码实现
const int N = 5e3 + 10;
int d[N][N], w[N];
string c[N];
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> c[i];
d[1][0] = 1;
for(int i = 2; i <= n; i++)
for(int j = i - 1; j >= 0; j--)
{
if(c[i - 1] == "f")
{
if(j) d[i][j] = d[i - 1][j - 1]; //如果没法缩进就是0喽
}
else{
d[i][j] = (d[i - 1][j] + d[i][j + 1]) % Mod;
}
}
int res = 0;
for(int i = 0; i < n; i++)
res = (res + d[n][i]) % Mod;
cout << res;
return;
}
Atcoder ABC322 E Prodect Development
题目理解
仔细读题后发现是个k维背包的问题，难点在于我们如何表示状态！！我们采用状态压缩表示
- 我们将
k维的压缩到1维，如何表示？就是将其转化为p + 1进制的数 - 这样我们就可以用一个特殊进制下的数，实现了
k维状态表示。 - 那么我们只需要写好状态即可。
/* 如果在体积为 j 的情况下且选择了第i个方案，的 p + 1进制表示为 g
那么我们可以得到：
f[i + 1][g] = min(f[i + 1][g], f[i - 1][j] + c[i])
如果我们没选:
f[i + 1][g] = min(f[i + 1][j], f[i][j])
代码实现
ll d[M][N], c[M], a[M][10];
ll n, k, p;
ll getid(vector<ll> v) // 得到p进制
{
ll res = 0;
for(ll i = 0; i < k; i++)
res = res * (p + 1) + v[i];
return res;
}
vector<ll> getv(ll u) // p进制转化成 k维
{
vector<ll> res;
for(ll i = 0; i < k; i++)
{
res.push_back(u % (p + 1));
u /= (p + 1);
}
reverse(res.begin(), res.end());
return res;
}
void solve()
{
cin >> n >> k >> p;
for(int i = 0; i < n; i++)
{
cin >> c[i];
for(int j = 0; j < k; j++)
cin >> a[i][j];
}
memset(d, LINF, sizeof d);
d[0][0] = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < N; j++)
{
if(d[i][j] < LINF)
{
d[i + 1][j] = min(d[i + 1][j], d[i][j]);
auto v = getv(j); //得到当前这个体积下对应的向量
// 更新这个向量, 得到如果选择了这个值会加到什么样子
for(int l = 0; l < k; l++)
v[l] = min(p, v[l] + a[i][l]);
ll g = getid(v); // 获取向量下对应的状态,转成p + 1状态下的数
d[i + 1][g] = min(d[i + 1][g], d[i][j] + c[i]);
}
}
vector<ll> res(k, p);
ll j = getid(res); // 得到答案应该是哪个状态
if(d[n][j] == LINF) cout << -1 << endl;
else cout << d[n][j] << endl;
return;
}
Div.4 Round871 A LoveStory
题目大意
问，一个长度为\(10\)的字符串，里面有几个和codeforces不一样。
题目理解
直接遍历即可
代码实现
void solve()
{
string tmp = "codeforces";
string s;
cin >> s;
int cnt = 0;
for(int i = 0; i < 10; i++)
if(s[i] != tmp[i])
cnt++;
cout << cnt << endl;
return;
}
Div.4 Round871 B Blank Space
题目大意
最长的0串有多长
题目理解
遍历一次，遇到1更新答案，遇到0就cnt++
代码实现
void solve()
{
int res = 0, cnt = 0;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int b;
cin >> b;
if(b == 1)
{
res = max(res, cnt);
cnt = 0;
}else cnt++;
}
res = max(cnt, res);
cout << res << endl;
return;
}
Div.4 Round871 C Mr. Perfectly Fine
题目大意
有n本书，每本书可以带来一个效果，01,10,11,00,0代表可以学会技能，1代表可以学会第二个技能。问我们学会技能的最小花费是多少。
题目理解
学会技能有两种途径：
- 一本书学会
- 两本数学会
所以存一下三种情况的最小值，然后输出两本书的和及一本书学会两者间小的。
代码实现
void solve()
{
int n;
cin >> n;
int time1 = INF, time2 = INF, time3 = INF;
for(int i = 1; i <= n; i++)
{
int b, c;
cin >> b >> c;
if(c == 0) continue;
if(c == 10)
time1 = min(time1, b);
else if(c == 1)
time2 = min(time2, b);
else if(c == 11)
time3 = min(time3, b);
}
if(time3 == INF && (time1 == INF || time2 == INF))
cout << -1 << endl;
else{
cout << min(time3, time1 + time2) << endl;
}
return;
}
Div.4 Round871 D Glod Rush
题目大意
给出两个数n和m，看能不能把n通过只分成\(2 / 3 * n 和 1 / 3 * n\)的方式得到m
题目理解
用个vector，存一下，只要是3的倍数都可以分，就只分三的倍数，分完的就标为-1即可。看过程中有没有出现m
代码实现
bool check(vector<int> a)
{
for(int i = 0; i < a.size(); i++)
if(a[i] % 3 == 0)
return true;
return false;
}
void solve()
{
int n, m;
cin >> n >> m;
if(m > n)
cout << "NO" << endl;
else if(m == n)
cout << "YES" << endl;
else{
vector<int> a;
a.push_back(n);
while(check(a))
{
for(int i = 0; i < a.size(); i++)
{
if(a[i] == m)
{
cout << "YES" << endl;
return;
}else{
if(a[i] % 3 == 0)
{
int t1 = a[i] / 3, t2 = a[i] / 3 * 2;
if(t1 == m || t2 == m)
{
cout << "YES" << endl;
return;
}
if(t1 % 3 == 0)
a.push_back(t1);
if(t2 % 3 == 0)
a.push_back(t2);
a[i] = 1;
}
}
}
}
cout << "NO" << endl;
}
return;
}
Div.4 Round871 E The Lakes
题目大意
问连通数字的，最大和是多少？
题目理解
BFS板子题，敲一遍即可
代码实现
const int N = 1010;
int n, m;
int g[N][N];
bool st[N][N];
int res = 0;
void bfs(int t1,int t2)
{
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};
queue<pair<int, int>> q;
q.push({t1, t2});
int d = g[t1][t2];
while(q.size())
{
auto t = q.front();
q.pop();
st[t.x][t.y] = true;
for(int i = 0; i < 4; i++)
{
int a = t.x + dx[i], b = t.y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && !st[a][b] && g[a][b] != 0)
{
d += g[a][b];
q.push({a, b});
st[a][b] = true;
}
}
}
res = max(res, d);
}
void solve()
{
memset(g, 0, sizeof g);
memset(st, 0, sizeof st);
res = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(!st[i][j] && g[i][j] != 0)
bfs(i, j);
cout << res << endl;
return;
}
Div.4 Round871 F Forever Winter
题目大意
问中心的点的度是多少，以及以它相连的点的度是多少。
题目理解
- 稠密图，用邻接矩阵存一下，有边的标记为
1 - 如果只有两种度，那么
x必为0 - 我们找到一个度为
1的点，然后遍历和它连结的点的度，找到一个度不为1的点就是x - 然后我们在找跟
x连结的点且度不为1的即可，就是y
代码实现
const int N = 210;
int k[N], g[N][N];
void solve()
{
memset(g, INF, sizeof g);
memset(k, INF, sizeof k);
int n, m, u, v;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &u, &v);
g[u][v] = g[v][u] = 1;
if(k[u] != INF && k[u] != 0) k[u]++;
if(k[v] != INF && k[v] != 0) k[v]++;
if(k[u] == INF) k[u] = 1;
if(k[v] == INF) k[v] = 1;
}
vector<int> a;
for(int i = 1; i <= n; i++)
if(k[i] != INF)
a.push_back(i);
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
if(a.size() == 2)
{
cout << a[1] << 0 << endl;
}else{
int flag;
for(int i = 1; i <= n; i++)
if(k[i] == 1)
{
flag = i;
break;
}
int x;
for(int i = 1; i <= n; i++)
if(g[flag][i] == 1 && k[i] != 1 && k[i] != INF)
{
x = k[i];
flag = i;
break;
}
int y;
for(int i = 1; i <= n; i++)
if(g[flag][i] == 1 && k[i] != 1 && k[i] != INF)
{
y = k[i];
break;
}
cout << y << " " << x - 1<< endl;
}
return;
}