题目链接：
http://codeforces.com/problemset/problem/214/B
Hometask
time limit per test：2 secondsmemory limit per test：256 megabytes
#### 问题描述
> Furik loves math lessons very much, so he doesn't attend them, unlike Rubik. But now Furik wants to get a good mark for math. For that Ms. Ivanova, his math teacher, gave him a new task. Furik solved the task immediately. Can you?
>
> You are given a set of digits, your task is to find the maximum integer that you can make from these digits. The made number must be divisible by 2, 3, 5 without a residue. It is permitted to use not all digits from the set, it is forbidden to use leading zeroes.
>
> Each digit is allowed to occur in the number the same number of times it occurs in the set.
#### 输入
> A single line contains a single integer n (1 ≤ n ≤ 100000) — the number of digits in the set. The second line contains n digits, the digits are separated by a single space.
#### 输出
> On a single line print the answer to the problem. If such number does not exist, then you should print -1.
#### 样例
>**sample input**
> 11
> 3 4 5 4 5 3 5 3 4 4 0
>
> **sample output**
> 5554443330
题意
给你一n个数x1,...,xn(0<=xi<=9)。挑出若干个拼在一起，使得它的值最大。
题解
题目相当于是求从n个数中挑出最多的数，它们的和能被3整除，并且它们中要有至少一个0，如果有多种方法挑出最多的数就优先选大的数挑。
可以用数位dp做：dp[i][j]表示考虑到第i个数，前缀和%3==j的方案数。
先对原序列排个序（为了转移的时候贪心挑最大的数），从左到右扫一遍dp，用pre[i][j]记录一下路径。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long LL;
string str;
int arr[maxn];
int dp[maxn][3], pre[maxn][3];
vector<int> ans;
int n, m;
int main() {
int zero = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}
sort(arr, arr + n);
memset(dp, -1, sizeof(dp));
for (int i = 0; i<maxn; i++) dp[i][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j<3; j++) {
dp[i][j] = dp[i - 1][j];
pre[i][j] = j;
int ne = ((j - arr[i]) % 3 + 3) % 3;
if (dp[i - 1][ne] >= 0 && dp[i][j] <= dp[i - 1][ne] + 1) {
dp[i][j] = dp[i - 1][ne] + 1;
pre[i][j] = ne;
}
}
}
int p = 0;
for (int i = n; i >= 1; i--) {
int bef = pre[i][p];
if (dp[i - 1][bef] + 1 == dp[i][p]) ans.push_back(arr[i]);
p = bef;
}
sort(ans.begin(), ans.end());
if (ans[0] != 0) {
puts("-1");
return 0;
}
int i = ans.size() - 1;
for (; i>0 && ans[i] == 0; i--);
for (; i >= 0; i--) printf("%d", ans[i]);
puts("");
return 0;
}