http://codeforces.com/contest/792/problem/C
这题奇葩题我居然用dp过了。
如果要模拟的话，可以用一个栈保存，保存每一个%3 = 2的pos，%3 = 1的pos，注意到题目是最多删除2个数，就能使得整个数%3=0了，如果要删除前导0的话就另外算。
那么贪心从栈顶删除，也就是先删除后面的数就行。然后需要删除2，又分两种情况，删除两个1和删除一个2。。等等，一路模拟。
比赛的时候没想到这样，也觉得很复杂，于是就dp了，虽然TLE了，但是加了一个剪枝就过了，dfs很玄
我用dp[i][j]表示，前i位中，模3后余数是j的最大合法长度，最大合法长度，也就是不能含有前导0.所以1001这样的情况求出来是无解的，需要特判一下。
那么求到了这个长度之后
题目就变成了，给出n个数字，选出k个，使得组合起来得数字%3 = 0，不能含有前导0.
我想不到好的算法，就dfs暴力了。感觉应该会超时，但是剪了剪支居然46ms
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e5 + 20; char str[maxn]; int dp[maxn][3], lenstr; //dp出答案 vector<char>ans; bool dfs(int cur, int now, int len, int pre) {if (now == 0 && len == dp[lenstr][0]) return true;if (cur == lenstr + 1) return false;if (len >= dp[lenstr][0]) return false;if (lenstr - cur + 1 + len < dp[lenstr][0]) return false;if (str[cur] == '0') {if (pre) {if (dfs(cur + 1, now, len + 1, 1)) {ans.push_back(str[cur]);return true;}return dfs(cur + 1, now, len, pre);} else {return dfs(cur + 1, now, len, pre);}} else {if (dfs(cur + 1, (now + str[cur] - '0') % 3, len + 1, 1)) {ans.push_back(str[cur]);return true;}return dfs(cur + 1, now, len, pre);} } void work() {scanf("%s", str + 1);lenstr = strlen(str + 1);memset(dp, -0x3f, sizeof dp);dp[0][0] = 0;int flag = inf;for (int i = 1; i <= lenstr; ++i) {if ((str[i] - '0') % 3 == 0) flag = i;for (int j = 0; j < 3 && i > 1; ++j) {dp[i][j] = dp[i - 1][j];}//不是0的，自己作为一个if (str[i] != '0') dp[i][(str[i] - '0') % 3] = max(dp[i][(str[i] - '0') % 3], 1);for (int j = 0; j < 3; ++j) {int res = (j * 10 + str[i] - '0') % 3;dp[i][res] = max(dp[i][res], dp[i - 1][j] + 1);}} // cout << dp[lenstr][0] << endl;if (dp[lenstr][0] < 0 && flag == inf) {cout << -1 << endl;return;}if (dp[lenstr][0] < 0 && flag != inf) {cout << str[flag];return;}dfs(1, 0, 0, 0);reverse(ans.begin(), ans.end());for (int i = 0; i < ans.size(); ++i) {cout << ans[i];} } int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; }