CodeForces 792C :Divide by Three DP + 路径还原

zz/2024/5/21 21:27:33

传送门

题目描述

在一个黑板上写着一个正整数 n 。它有不超过10^5位(话说黑板上是怎么写下这个数的) 。老师给你了一个任务,把它魔改成一个 美丽数 ,而且因为你很懒,你非常非常的想用最小的步数把它改成一个 美丽数 。

美丽数 ,就是一个不含前导0,是3的倍数且位数大于零的正整数。举个栗子例子,0、99、10110都是 美丽数 ,但00、03、122都不是。

你决定写一个程序来帮助你的老师来完成这个无聊的任务。你的要求就是用最小的步数来完成这个任务。

如果不可能通过删数来达到 美丽数 ,输出-1。如果有多个最优解答案,输出任意一个即可。

分析

fi][j]表示当前为第i时,余数为j的情况下要擦去多少位数字
需要注意的情况是,如果当前位置为0,前面擦去了i - 1位数字时,那么这一位数字必须要擦除,可以根据状态转移方程推出来
然后路径还原一下即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int a[N];
char str[N];
int pre[N][3];
int f[N][3];
int n;int main(){scanf("%s",str + 1);n = strlen(str + 1);memset(f,0x3f,sizeof f);memset(pre,-1,sizeof pre);for(int i = 1;i <= n;i++) a[i] = (str[i] - '0') % 3;f[1][0] = 1;f[1][a[1]]=0;for(int i = 2;i <= n;i++){for(int j = 0;j < 3;j++) {f[i][j] = f[i - 1][j] + 1;pre[i][j] = j;if(((str[i] - '0') == 0) && f[i - 1][j] == i - 1) continue;if(f[i][j] > f[i - 1][(j - a[i] + 3) % 3]){f[i][j] = f[i - 1][(j - a[i] + 3) % 3];pre[i][j] = (j - a[i] + 3) % 3;}}}if(f[n][0] == n){for(int i = 1;i <= n;i++) if(str[i] - '0' == 0) {puts("0");return 0;}puts("-1");return 0;}int p = 0;stack<int> ans;for(int i = n;i;i--){int back = p;p = pre[i][p];if(f[i][back] == f[i - 1][p]) ans.push(str[i] - '0');}if(!ans.size()){puts("-1");return 0;}while((ans.top() == 0) && ans.size() != 1) ans.pop();while(ans.size()){printf("%d",ans.top());ans.pop();}return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/zz/2727389.html

相关文章

CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

传送门 题目描述 给出N个位子&#xff0c;排成一列&#xff0c;现在有M个烟花&#xff0c;每秒人的速度d&#xff0c;每个烟花有三个元素&#xff1a;a&#xff0c;b&#xff0c;t&#xff0c;表示在时刻t会绽放&#xff0c;如果我们在位子x观看到了的话&#xff0c;会获得b-…

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点&#xff0c;求是否存在两条直线穿过所有点。 分析 前面三个点中&#xff0c;任意两个点必成一条直线&#xff0c;所以我们去枚举三个点中的两个&#xff0c;然后去判断其他的点是否在这条直线上&#xff0c;然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排&#xff08;顺序是乱的&#xff09;&#xff0c;每人手中拿着一把枪。每一个时刻&#xff0c;每个人同时瞄准右边的人&#xff08;如果存在的话&#xff09;&#xff0c;然后如果这个人编号比自己大&#xff0c;则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下&#xff0c;在trie图上的位置位j的情况下匹配情况位k&#xff0c;状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态&#xff0c;节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串&#xff0c;你从中挑选一些让它们成为一个环&#xff0c;使得这个环朝一个方向转 k k k下&#xff0c;与原来看起来一样&#xff0c;找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子&#xff0c;那么我转…

POJ - 3635 :Full Tank? 最短路 + 拆点

分析 跟前段时间看的一个拆点求邻接矩阵快速幂的一个题有点像 这个题比较朴素的方法就是我把每个点剩余 j j j单位的汽油的最低花费处理出来&#xff0c;然后这样写毫无疑问会tle&#xff0c;所以我们需要去进行一些优化 首先我们思考一下这个朴素的思想为什么会超时&#xff…

CodeForces 546E :Soldier and Traveling 网络流 +拆点

传送门 题目描述 题意大概就是给定 n n n 个城市&#xff0c; m m m 条边。 然后人只能从走相邻边相连的城市。 现在给你初始城市的每一个人数&#xff0c;再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能&#xff0c;输入“YES”并输出方案&#xff0…

CodeForces 1312E : Array Shrinking 区间DP

传送门 题目描述 给你一个序列 a i a_{i} ai​&#xff0c;相邻两个数如果相同的话&#xff0c;我们可以删去其中一个数字&#xff0c;另一个数字1&#xff0c;最后留下来的序列最小可以是多少 分析 这个数据范围大概就能想到是区间DP问题了 我们首先初始化每一个区间f[i][…

CodeForces 1447D :Catching Cheaters 字符串DP

传送门 题目描述 给我们两个字符串&#xff0c;让我们从中选出两个字串&#xff0c;算出它们的最大公共子序列长度。然后将它乘4在减去两个字串的长度。问你这个数最大是多少。 分析 我们可以把这个式子转换为2 * LIS - a的剩余长度 - b的剩余长度&#xff0c;然后就可以设…

重建道路:树形DP

传送门 题目描述 分析 去年写的题&#xff0c;今天看猫猫博客的时候又想起来了这道题&#xff0c;回顾一些细节 f [ i ] [ j ] f[i][j] f[i][j]表示以 i i i为根节点保留 j j j个节点所要砍掉的道路数量&#xff0c;然后跑一下树形背包即可 代码 #include <bits/stdc.h…