Problem I Rank LED题解

题目大意

‘0’到‘9’的数字亮线依次为{6、2、5、5、4、5、6、3、7、6}。

Luras想修改每条光线的位置，使她的新等级尽可能小，同时新等级也是一个不带任何前导零的正整数。

另外，光线总数应与开始时相同。

官方题解

思路

这题一开始想的是无脑换成8结尾，但发现不行，比如 输入 23 输出 22

还是得用dp来解，当然可以尝试打表看看有没有规律啥的

使用 dp 通过打表发现规律（发现208及其之后的都是以8结尾）

所以可以用比较偷懒的写法：把208（灯管长度18）之前的保存起来，当特例判断。之后的就直接贪（只要判断其中几个数字就行），直接从后往前输出

参考代码c++（官方题解思路dp写法）

感谢 2023牛客寒假集训营训练营3 QQ群的 [文件]第十五届蓝桥杯国赛获奖名单.pdf 同学的DP代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;const int N = 7e2 + 5;
string dp[N];
int t, n;
string s;vector<string> a = {"1", "7", "4", "2", "0", "6", "8"};
vector< int >  b = { 2,  3,  4,  5,  6,  6,  7 };
int arr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};string MinStr(string a, string b) {if (a[0] == 'f') {return b;}if (a.size() < b.size()) {return a;}if (a.size() > b.size()) {return b;}for (int i = 0; i < int(a.size()); i++) {if (a[i] < b[i]) {return a;}if (a[i] > b[i]) {return b;}}return a;
}string Merge(string a, string x) {string str = "";if (x[0] == '0') {str += a[0];str += x;for (int i = 1; i < int(a.size()); i++) {str += a[i];}return str;}bool flag = true;for (int i = 0; i < int(a.size());) {if (flag && x[0] <= a[i]) {flag = false;str += x;} else {str += a[i++];}}if (flag) {str += x;}return str;
}int main() {for (int i = 0; i <= 700; i++) {dp[i] = "f";}dp[2] = "1", dp[3] = "7", dp[4] = "4", dp[5] = "2", dp[6] = "6", dp[7] = "8";for (int i = 8; i <= 700; i++) {for (int j = 0; j < int(a.size()); j++) {dp[i] = MinStr(dp[i], Merge(dp[i - b[j]], a[j]));}}//	dp输出所有结果
//	for (int i = 0; i <= 70; i++) {
//		cout << dp[i] << '\t';
//		if (i % 10 == 9) {
//			cout << endl;
//		}
//	}cin >> t;while (t--) {cin >> n >> s;int x = 0;for (int i = 0; i < int(s.size()); i++) {x += arr[s[i] - '0'];}cout << dp[x] << endl;}return 0;
}