题意:给指定数量的数字“1”,“2”,“3”……,“9”。用所有这些数字加上任意个0组成一个数,要求数能被11整除,且数的位数尽量小。
能被11整除的数有一个特点,奇数位数字之和与偶数位之和的差为11的倍数。
所以想到把所有数字分成两部分,即奇数位部分和偶数位部分,两部分的差相0即能被11整除(MOD 11)。
所求可以化为,其中一部分%11的余数为所有数字之和%11的余数的一半。
dp[k][r] := 能否找到 任意k个数之和 %11 == R
#include<bits/stdc++.h> using namespace std; int dig[12]; bool dp[105][12]; int main() { int t; scanf("%d", &t); while (t--) { int n = 0; //数字个数 int sum = 0; //所有数字之和 memset(dp, 0, sizeof dp); for (int i = 1; i <= 9; ++i) { scanf("%d", dig + i); n += dig[i]; sum += dig[i] * i; } int m = sum % 11; if (m & 1) m += 11; m /= 2; dp[0][0] = true; for (int i = 1; i <= 9; ++i) { for (int j = 0; j < dig[i]; ++j) { for (int k = n; k >= 1; --k) { //for (int k = 1; k <= n; ++k) { for (int r = 0; r < 11; ++r) { dp[k][r] |= dp[k - 1][(r - i + 11) % 11]; } } } } int flag = 1; for (int i = n / 2; i >= 0; --i) { if (dp[i][m]) { printf("%d\n", n + max(n - i - 1 - i, 0)); flag = 0; break; } } if (flag) { printf("-1\n"); } } return 0; }