V
主页
京东 11.11 红包
四星级编程题解析——巧背圆周率(动态规划)
发布人
上海市计算机学会竞赛平台——四星级题目解析: 巧背圆周率 学习如何简单的动态规划 题目链接:上海市计算机学会竞赛平台 | YACS (iai.sh.cn) #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e5 + 10; int dp[maxn]; int diff[maxn][7];// diff[i][k] :从i位置往前的k个字符片段的记忆难度 void cal(string s, int n) { for (int i = 3; i <= n; i++) { if (s[i] - s[i - 1] == s[i - 1] - s[i - 2]) { if (s[i] - s[i - 1] == 0) diff[i][3] = 1; else if (s[i] - s[i - 1] == 1 || s[i] - s[i - 1] == -1) diff[i][3] = 2; else diff[i][3] = 5; } else { if (s[i] == s[i - 2]) diff[i][3] = 4; else diff[i][3] = 10; } } for (int k = 4; k <= 6; k++) { for (int i = 4; i <= n; i++) { if (diff[i - 1][k - 1] == 1 && s[i] == s[i - 1]) diff[i][k] = 1; else if (diff[i - 1][k - 1] == 2 && s[i] - s[i - 1] == s[i - 1] - s[i - 2]) diff[i][k] = 2; else if (diff[i - 1][k - 1] == 5 && s[i] - s[i - 1] == s[i - 1] - s[i - 2]) diff[i][k] = 5; else if (diff[i - 1][k - 1] == 4 && s[i] == s[i - 2]) diff[i][k] = 4; else diff[i][k] = 10; } } } int main() { string s; cin >> s; int n = s.size(); s = '0' + s; cal(s, n); memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[0] = 0; for (int i = 3; i <= n; i++) { for (int k = 3; k <= 6; k++) { //防止i-k越界 if (i - k < 0) continue; dp[i] = min(dp[i], dp[i - k] + diff[i][k]); //状态转移方程 } // cout << i << " " << dp[i] << endl; } cout << dp[n]; return 0; }
打开封面
下载高清视频
观看高清视频
视频下载器
四星级编程题解析——切香肠
一星级编程题——空心正方形(解析赛场注意事项,避免0分,支你9招)
编程题解析——双重质数( 埃氏筛法的三处难点)
四星级编程题解析——最大割(美妙的优先队列+分支限界法)
五星级编程题解析——树的直径( 动态规划方法 )
四星级编程题解析——平安数(深度搜索 + 记忆化)
一星级编程题解析——阶乘的余数
四星级编程题解析——洗牌(捕捉隐含的循环节)
四星级编程题——数三角形(方案2)避坑经验分享
滚动数组 ——0烦恼的实现方式
四星级编程题解析——看小说(二分法)
判断是几位数(3个办法,哪个更简单?)
2024年泰兴市编程赛初中组第4题—— 编码(线性动态规划)
快速斐波那契数(快速幂运算)
四星级编程题解析——三扔硬币
四星级编程题解析:数三角形(方案1)
六星级编程题解析——无尽的循环(一题搞定“扩展欧几里得算法”)
四星级编程题解析——跑步
三星级编程题解析——异或延展
[入门篇]从入门到信息奥赛,最新C++编程基础(青少年、零基础、小白皆能学懂)C++程序设计快速学
三星级编程题解析——平衡点
2024年泰兴市编程赛 初中组第3题:01串(深度搜索和宽度搜索)
三星级编程题解析——异或方程
典型例题解析——阶乘的和
三星级题目解析——改造序列
二星级题目解析——珠玑妙算(一)
蓝桥杯2023省赛编程题(中低难度部分)
编程题解析——冰雹来袭(练习宽搜)
三星级编程题解析——伙伴关系
三星级编程题解析—加与乘(巧妙思路)
典型编程题解析——风车
2024年泰兴市编程赛 初中组第5题:跑步(动态规划基本题)
二星级编程题解析——阶乘尾零
一星级题目解析——三角形分类
《60天刷爆CSP》前言框架
模拟试题——程序设计部分
一星级题目解析——竞选班长
四星级编程题解析——淘气合影(数组,排序)
五星级编程题解析——围三角(动态规划 0/1背包问题)
典型编程题目解析——组队竞赛(熟悉双指针+前缀和)