[转载]codeforces 792CDivide by Three（两种方法：模拟、动态规划

#include<bits/stdc++.h>
using namespace std;
char s[100010];
int a[3];
int t,flag,n,p;
int main(){scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++){t=(t+s[i])%3;a[s[i]%3]++;}//相加和为0直接输出if(!t){puts(s+1);return 0;}for(p=2;s[p]=='0';p++);p-=2;if(a[t]&&n>1&&(p<=1||a[t]>1||s[1]%3!=t)) a[t]--;else if(a[3-t]>1&&n>2) a[3-t]-=2;else if(a[t]&&n>1) a[t]--;else {puts("-1");return 0;}/*t==1，那么我们可以删去一个模3等于1的数字位，或者删去两个模3等于2的数字位（这个很容易漏）。*//*t==2，可以删去一个模3等于2的数字位，或者删去两个模3等于1的数字位。*/for(int i=1;i<=n;i++){if(s[i]=='0'&&!flag) continue;if(a[s[i]%3]) {putchar(s[i]);a[s[i]%3]--;flag=1;} }if(!flag) puts("0");
}

#include<bits/stdc++.h>
using namespace std;
const int mod = 3;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
int dp[maxn][3];
int pre[maxn][3];
char str[maxn];
char ans[maxn];
int main(){while(cin>>str){int n=strlen(str);if(n==1){if((str[0]-'0')%3==0) printf("%c\n",str[0]);else printf("-1\n");continue;}memset(pre,-1,sizeof(pre));memset(dp,INF,sizeof(dp));dp[0][0]=1;dp[0][(str[0]-'0')%3]=0;for(int i=1;i<n;i++){for(int j=0;j<3;j++){if(dp[i-1][j]+1<dp[i][j]){dp[i][j]=dp[i-1][j]+1;pre[i][j]=j;}if((str[i]-'0')%3==0){if(str[i]=='0'){if(dp[i-1][j]!=i&&dp[i-1][j]<dp[i][j]){dp[i][j]=dp[i-1][j];pre[i][j]=j;} }else{if(dp[i-1][j]<dp[i][j]){dp[i][j]=dp[i-1][j];pre[i][j]=j;} }}if((str[i]-'0')%3==1&&dp[i-1][((j-1)%mod+mod)%mod]<dp[i][j]){dp[i][j]=dp[i-1][((j-1)%mod+mod)%mod];pre[i][j]=((j-1)%mod+mod)%mod;}if((str[i]-'0')%3==2&&dp[i-1][((j-2)%mod+mod)%mod]<dp[i][j]){dp[i][j]=dp[i-1][((j-2)%mod+mod)%mod];pre[i][j]=((j-2)%mod+mod)%mod;} }}if(dp[n-1][0]==n){int flag=0;for(int i=0;i<n;i++){if(str[i]=='0') flag=1;} if(flag==1) printf("0\n");else printf("-1\n");continue;}int cnt=0;int now=n-1;int j=0;while(now>=1){int pree=pre[now][j];if(dp[now-1][pree]==dp[now][j]){ans[cnt++]=str[now];}j=pree;now--;if(now==0){if(pree==(str[0]-'0')%3){ans[cnt++]=str[now];} }}for(int i=cnt-1;i>=0;i--){printf("%c",ans[i]);}printf("\n");}
}