题目

{% fold 点击显/隐题目 %}

Mr. Fib is a mathematics teacher of a primary school. In the next lesson, he is planning to teach children how to add numbers up. Before the class, he will prepare N cards with numbers. The number on the i-th card is ai. In class, each turn he will remove no more than 3 cards and let students choose any ten cards, the sum of the numbers on which is 87. After each turn the removed cards will be put back to their position. Now, he wants to know if there is at least one solution of each turn. Can you help him?
The first line of input contains an integer t(t≤5), the number of test cases. t test cases follow. For each test case, the first line consists an integer N(N≤50). The second line contains N non-negative integers a1,a2,...,aN. The i-th number represents the number on the i-th card. The third line consists an integer Q(Q≤100000). Each line of the next Q lines contains three integers i,j,k, representing Mr.Fib will remove the i-th, j-th, and k-th cards in this turn. A question may degenerate while i=j, i=k or j=k.
For each turn of each case, output 'Yes' if there exists at least one solution, otherwise output 'No'.
1 12 1 2 3 4 5 6 7 8 9 42 21 22 10 1 2 3 3 4 5 2 3 2 10 10 10 10 11 11 10 1 1 1 2 10 1 11 12 1 10 10 11 11 12
No No No Yes No Yes No No Yes Yes
{% endfold %}

题解

按照动态规划的思想,有：
dp[i][j][k] = dp[i-1][j][k] | dp[i-1][j-1][k-num[i]]
其中 dp[i][j][k] 表示前 i 个数中选择 j 个数能否达到 k

虽然这道题涉及到的 i j k 都比较小,但是由于查询次数达到 100000,还是不能直接动态规划做

对于动态规划部分,可以使用bitset压缩,能够省去 k 的枚举
由于 dp[i][][] 的值取决于 dp[i-1][][] ,因此这一维是不需要单独记录的
用 dp[i] 表示选取 i 个数的情况下,bitset的各位能否达到
则可以得到转移方程 dp[t] |= dp[t-1] << num[i]
其中,<< num[i]表示把 dp[t-1] 整体左移 num[i] 位(相当于一次完成k维的工作)

需要特别注意的是,t 维的循环应该从大到小循环(因为省去了 i 的情况下,从小到大的运算顺序是错的)

另外,这道题的时限是比较紧的,各个部分都需要优化,输入也要用输入优化

代码

{% fold 点击显/隐代码 %}```cpp Eighty seven https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 51;

int num[maxn];
bitset<90> dp[11];

int ans[maxn][maxn][maxn];
int n;

int read_int() {
char c;
int ans = 0;
while (c = getchar(), !(c >= '0' && c <= '9'))
;
while (c >= '0' && c <= '9') {
ans *= 10;
ans += (int)c - '0';
c = getchar();
}
return ans;
}

bool getAns(int a, int b, int c) {
if (ans[a][b][c] == -1) {
for (int i = 0; i <= 10; i++)
dp[i].reset();
dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        if (i != a && i != b && i != c)
            for (int t = 10; t >= 1; --t)
                dp[t] |= dp[t - 1] << num[i];
    }

    ans[a][b][c] = dp[10][87];
}
return ans[a][b][c] == 1;

}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int START = clock();
#endif

int T = read_int();
while (T--) {
    memset(ans, -1, sizeof(ans));

    n = read_int();
    for (int i = 1; i <= n; ++i)
        num[i] = read_int();

    int Q = read_int();
    int a[3];
    for (int q = 0; q < Q; ++q) {
        a[0] = read_int(), a[1] = read_int(), a[2] = read_int();
        sort(a, a + 3);
        printf("%s\n", (getAns(a[0], a[1], a[2]) ? "Yes" : "No"));
    }
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}