<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
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?
</div><div class="part" title="Input">
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.
</div><div class="part" title="Output">
For each turn of each case, output 'Yes' if there exists at least one solution, otherwise output 'No'.
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
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
</div><div class="output part" title="Sample Output">
No
No
No
Yes
No
Yes
No
No
Yes
Yes
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>按照动态规划的思想,有：<br>
<code>dp[i][j][k] = dp[i-1][j][k] | dp[i-1][j-1][k-num[i]]</code><br>
其中 <code>dp[i][j][k]</code> 表示前 <code>i</code> 个数中选择 <code>j</code> 个数能否达到 <code>k</code></p>
<p>虽然这道题涉及到的 <code>i</code> <code>j</code> <code>k</code> 都比较小,但是由于查询次数达到 <code>100000</code>,还是不能直接动态规划做</p>
<p>对于动态规划部分,可以使用<strong>bitset</strong>压缩,能够省去 <code>k</code> 的枚举<br>
由于 <code>dp[i][][]</code> 的值取决于 <code>dp[i-1][][]</code> ,因此这一维是不需要单独记录的<br>
用 <code>dp[i]</code> 表示选取 <code>i</code> 个数的情况下,bitset的各位能否达到<br>
则可以得到转移方程 <code>dp[t] |= dp[t-1] &lt;&lt; num[i]</code><br>
其中,<code>&lt;&lt; num[i]</code>表示把 <code>dp[t-1]</code> 整体左移 <code>num[i]</code> 位(相当于一次完成<code>k</code>维的工作)</p>
<p>需要特别注意的是,<code>t</code> 维的循环应该从大到小循环(因为省去了 <code>i</code> 的情况下,从小到大的运算顺序是错的)</p>
<p>另外,这道题的时限是比较紧的,各个部分都需要优化,输入也要用输入优化</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp Eighty seven  <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
/<em>/<br>
#define debug<br>
#include <ctime><br>
//</em>/<br>
#include <algorithm><br>
#include <bitset><br>
#include <cstdio><br>
#include <cstring><br>
#include <iostream><br>
using namespace std;</p>
<p>const int maxn = 51;</p>
<p>int num[maxn];<br>
bitset&lt;90&gt; dp[11];</p>
<p>int ans[maxn][maxn][maxn];<br>
int n;</p>
<p>int read_int() {<br>
char c;<br>
int ans = 0;<br>
while (c = getchar(), !(c &gt;= '0' &amp;&amp; c &lt;= '9'))<br>
;<br>
while (c &gt;= '0' &amp;&amp; c &lt;= '9') {<br>
ans *= 10;<br>
ans += (int)c - '0';<br>
c = getchar();<br>
}<br>
return ans;<br>
}</p>
<p>bool getAns(int a, int b, int c) {<br>
if (ans[a][b][c] == -1) {<br>
for (int i = 0; i &lt;= 10; i++)<br>
dp[i].reset();<br>
dp[0][0] = 1;</p>
<pre><code>    for (int i = 1; i &lt;= n; ++i) {
        if (i != a &amp;&amp; i != b &amp;&amp; i != c)
            for (int t = 10; t &gt;= 1; --t)
                dp[t] |= dp[t - 1] &lt;&lt; num[i];
    }

    ans[a][b][c] = dp[10][87];
}
return ans[a][b][c] == 1;
</code></pre>
<p>}</p>
<p>int main() {<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
// freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);<br>
int START = clock();<br>
#endif</p>
<pre><code>int T = read_int();
while (T--) {
    memset(ans, -1, sizeof(ans));

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

    int Q = read_int();
    int a[3];
    for (int q = 0; q &lt; Q; ++q) {
        a[0] = read_int(), a[1] = read_int(), a[2] = read_int();
        sort(a, a + 3);
        printf(&quot;%s\n&quot;, (getAns(a[0], a[1], a[2]) ? &quot;Yes&quot; : &quot;No&quot;));
    }
}
</code></pre>
<p>#ifdef debug<br>
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);<br>
#endif<br>
return 0;<br>
}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

HDU 5890.Eighty seven