Codeforce 792C(dp)

本文主要是介绍Codeforce 792C(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：给出一个数字，要求删除最少的位数，使得删除后的数字不含前导0并且是3的倍数

代码：

#include <set>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
vector<char> G;
char s[100005];
int dp[100005][5],pre[100005][5];
int main(){int n,i,j,u,v,tmp;while(scanf("%s",s+1)!=EOF){n=strlen(s+1);memset(dp,-1,sizeof(dp));memset(pre,-1,sizeof(pre));for(i=1;i<=n;i++)dp[i][0]=0;                             //dp[i][j]表示到第i为，%3==j时，最多保留几个数字pre[i][0]=0;dp[1][(s[1]-'0')%3]=1;pre[1][(s[1]-'0')%3]=1;for(i=2;i<=n;i++){for(j=0;j<3;j++){if(dp[i-1][j]!=-1){if(dp[i][j]<dp[i-1][j]){pre[i][j]=0;            //去掉当前位dp[i][j]=dp[i-1][j];}if(dp[i-1][j]==0&&s[i]=='0')//如果前面都要去并且当前位为0，那么当前位不能位首位continue;if(dp[i][(j+s[i]-'0'+3)%3]<dp[i-1][j]+1){pre[i][(j+s[i]-'0'+3)%3]=1;dp[i][(j+s[i]-'0'+3)%3]=dp[i-1][j]+1;}                           //保留当前位}}}if(dp[n][0]==0){                        //dp[n][0]为0则表示需要全部去掉for(i=1;i<=n;i++){                  //那么有两种情况，一种是结果为0，一种是不存在if(s[i]=='0')goto next;}puts("-1");continue;next:puts("0");continue;}G.clear();u=n,v=0;while(u){                               //直接逆序输出tmp=pre[u][v];if(tmp==1){G.push_back(s[u]);v=(v-(s[u]-'0')%3+3)%3;}u--;}for(i=G.size()-1;i>=0;i--)printf("%c",G[i]);printf("\n");}return 0;
}

这篇关于Codeforce 792C(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---