Codeforces Round #748 (Div. 3) F - Red-Black Number （记忆化搜索）

网友投稿 682 2022-11-17

Codeforces Round #748 (Div. 3) F - Red-Black Number （记忆化搜索）

Codeforces Round #748 (Div. 3) F - Red-Black Number （记忆化搜索）

​​linkkk​​

题意

思路

代码

#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;int n, a, b, ans, col[55], dp[55][55][55][55];string s;int st[55];void dfs(int u, int ma, int mb, int cnta) { if (u == n) { if (!ma && !mb && cnta >= 1 && cnta < n) { if (abs(n - cnta - cnta) < ans) { ans = abs(n - cnta - cnta); for (int i = 0; i < n; i++) col[i] = st[i]; } } return; } if (dp[u][ma][mb][cnta]) return; dp[u][ma][mb][cnta] = 1; st[u] = 0; dfs(u + 1, (ma*10 + s[u] - '0') % a, mb, cnta + 1); st[u] = 1; dfs(u + 1, ma, (mb*10 + s[u] - '0') % b, cnta);}int main() { int _; cin >> _; while (_--) { cin >> n >> a >> b; cin >> s; ans = 1e9; memset(dp, 0, sizeof dp); dfs(0, 0, 0, 0); if (ans == 1e9) puts("-1"); else { for (int i = 0; i < s.size(); i++) if (col[i]) cout << "B"; else cout << "R"; puts(""); } } return 0;}/*45 3 13021654 2 113578 1 1123456782 7 990*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:【15】进大厂必须掌握的面试题-容器化和虚拟化面试
下一篇:Axure教程汇总
相关文章

 发表评论

暂时没有评论，来抢沙发吧~