马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题目描述
小明最近在研究一个数字删除游戏，正要考考佳佳。游戏规则如下：
给定一个正整数，去掉此中多少个数字后剩下的数字按原左右次序将组成一个新的正整数。叨教最少删去几个数字，能够使得这个新的正整数合法(不含前导0)且是3的倍数。
小明写下的数字太大，佳佳一时处置惩罚不了。请你帮他写一个步伐处置惩罚出结果吧!
输入
第一行一个整数n，表示小明写下了n正整数。
第2~n+1行每行一个正整数Ai。
输出
共n行，每行一个整数，表示最少删去的数字的个数。假如没有合法的方案，请输出“ERR”(不含引号)。
样例
输入样例
3
1234
1000
2
输出样例
1
3
ERR
提示
【样例表明】
第一组删除1个留下的整数为234或123.
第二组删除3个留下的整数为0。
对于30%的数据，n≤5，Ai≤ 1 0 9 10^9 109且不含有数字0。
对于60%的数据，n≤5，A¡≤ 1 0 100000 10^{100000} 10100000且不含有数字0.
对于100%的数据，n≤5，Ai≤ 1 0 100000 10^{100000} 10100000 。(数字的长度可能达到100001位)
分析
可以用动态规划来办理（线性dp）
由于要求不含前导零，所以从后往前转移。
f[j]代表 第i位到最后一位组成的数，对3取模等于j时最少必要删的数字的数目
令a指 第i位数字模3的结果
则对于第i位数字，有删除和不删除两种情况
若删除，则f[j] = f[i + 1][j] + 1
若不删除，则f[j] = f[i + 1][(j - a + 3) % 3](注意j - a可能为负数，故必要进行处置惩罚)
最终状态转移方程为
f[j] = min(f[i + 1][j] + 1,f[i + 1][(j - a + 3) % 3])
对于最终结果，
起首，我们可以枚举i作为最终正整数的起始位置，
假如当前s不为‘0’时，则代表可以枚举，即将前 i - 1 个数字全部删去，且保留第i位数字，则局部最优解为
i - 1 + f[i + 1][(0 - a + 3) % 3] (即把状态转移方程的j替换为0)，最终结果取最小值即为答案
ps.由于第i位必要保留，所以不能是 i - 1 + f[0]
又由于最后一位数字不肯定能被3整除，所以只能从1枚举到len - 1，
若最有一位数字能被3整除，那加一个特判 res = min(res,len - 1)即可
代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 100000 + 10,INF = 0x3f3f3f3f;
- int n;
- char s[N];
- int a[N];
- int f[N][3];
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0),cout.tie(0);
- cin >> n;
- while(n--){
- cin >> s + 1;
- int len = strlen(s + 1);
- for(int i = 1;i <= len;i++) a[i] = (s[i] - '0') % 3;
- //初始化
- memset(f,0x3f,sizeof f);
- f[len][a[len]] = 0;
- if(a[len]) f[len][0] = 1;
- for(int i = len - 1;i >= 1;i--)
- for(int j = 0;j <= 2;j++)
- f[i][j] = min(f[i + 1][j] + 1,f[i + 1][(j - a[i] + 3) % 3]);
-
- int res = INF;
- for(int i = 1;i < len;i++)
- if(s[i] != '0') res = min(res,i - 1 + f[i + 1][(0 - a[i] + 3) % 3]);
- if(a[len] == 0) res = min(res,len - 1); // 特判
- if(res == INF) cout << "ERR\n";
- else cout << res << '\n';
- }
- return 0;
- }
|
