<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
《snow halation》是μ’s的第二张单曲，其歌曲第二段伴奏结束后主唱穗乃果唱出“届けて”的同时，全场应援棒瞬间从白色转换成橙色。由于高度的整齐和效果的震撼，被称为“橙色的奇迹”，这也是“如果奇迹有颜色，那么一定是XX色”的最早来源。
<p><div class='image'><a href='//static.oyohyee.com/post/aoj901.jpg' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/aoj901.jpg" /></a></div></p>
<p>现在，到了你来应援的时候了！</p>
<p>使用不同的应援形式有不同的效果（如里打、里跳、快挥、前挥、GT警报……），比如通常会GT警报后接着做里跳，这样能够让人更加沉迷到演唱会的气氛中。<br>
经过精密的计算，我们终于得到了不同的应援形式连着对活跃气氛的贡献值（增加气氛的活跃值）。</p>
<p>现在给你一首歌的call表(记录应该如何应援)，里面有一部分是0（代表这个动作可以自己随意选择），另一部分是非0整数，表示这个时候有规定的动作要做。<br>
求这首歌能达到的最大气氛活跃值。<br>
初始的气氛活跃值为0，第一个应援动作对气氛无影响。</p>
<p>样例解释：<br>
2<br>
3 5<br>
83 86 77<br>
15 93 35<br>
86 92 49<br>
3 3 3 1 2</p>
<p>3 3 3 1 2<br>
没有可以自己随便选的,直接计算得到49+49+86+86=270</p>
<p>5 10<br>
36 11 68 67 29<br>
82 30 62 23 67<br>
35 29 2 22 58<br>
69 67 93 56 11<br>
42 29 73 21 19<br>
0 0 5 0 4 0 0 0 4 0</p>
<p>4 3 5 1 4 1 4 1 4 5<br>
按照这样的顺序来选<br>
可以达到最大值 93+58+42+67+69+67+69+67+93=625</p>
</div><div class="part" title="Input">
第1行：组数T（非负整数，1&lt;=T&lt;=10）
第2行：应援动作数n，call表长度m（非负整数，0&lt;=n，m&lt;=100）
第3~3+n行：每行n个整数，表示在第i个动作后接j的气氛贡献值，Wi,j表示当前行第j个。（|Wi,j|&lt;=100）
第4+n行：m个非负整数a[i]，表示call表内容。（0&lt;=a[i]&lt;=n）
……
</div><div class="part" title="Output">
一行，一个整数，表示能达到的最大气氛活跃值。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
2
3 5
83 86 77
15 93 35
86 92 49
3 3 3 1 2
5 10
36 11 68 67 29
82 30 62 23 67
35 29 2 22 58
69 67 93 56 11
42 29 73 21 19
0 0 5 0 4 0 0 0 4 0
</div><div class="output part" title="Sample Output">
270
625
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>修改自 <a href="/post/HDU/5074.html">HDU 5074.Hatsune Miku(2014 鞍山赛区现场赛 E)</a></p>
<p>需要额外考虑<strong>活跃贡献值为负数</strong>的情况</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp snow halation <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <algorithm><br>
#include <cstdio><br>
using namespace std;</p>
<p>const int maxn = 105;<br>
const int INF = 99999;</p>
<p>int n, m;<br>
int a[maxn];<br>
int dp[maxn][maxn];<br>
int w[maxn][maxn];</p>
<p>// 初始化</p>
<p>void init() {<br>
for (int i = 0; i &lt;= m; ++i)<br>
for (int j = 0; j &lt;= n; ++j)<br>
if (i == 1)<br>
dp[i][j] = 0;<br>
else<br>
dp[i][j] = -INF;<br>
}</p>
<p>// 进行 dp<br>
void f(int i, int l, int t) {<br>
if (dp[i][t] == -INF)<br>
dp[i][t] = dp[i - 1][l] + w[l][t];<br>
else<br>
dp[i][t] = max(dp[i][t], dp[i - 1][l] + w[l][t]);<br>
}</p>
<p>// 枚举 t<br>
void T(int i, int l) {<br>
if (a[i] == 0) {<br>
for (int t = 1; t &lt;= n; ++t)<br>
f(i, l, t);<br>
} else {<br>
f(i, l, a[i]);<br>
}<br>
}</p>
<p>// 枚举 l<br>
void L(int i) {<br>
if (a[i - 1] == 0) {<br>
for (int l = 1; l &lt;= n; ++l)<br>
T(i, l);<br>
} else {<br>
T(i, a[i - 1]);<br>
}<br>
}</p>
<p>int main() {<br>
//freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);<br>
int T;<br>
scanf(&quot;%d&quot;, &amp;T);<br>
while (T--) {<br>
// 读入数据<br>
scanf(&quot;%d%d&quot;, &amp;n, &amp;m);</p>
<pre><code>    for (int i = 1; i &lt;= n; ++i)
        for (int j = 1; j &lt;= n; ++j)
            scanf(&quot;%d&quot;, &amp;w[i][j]);

    for (int i = 1; i &lt;= m; ++i)
        scanf(&quot;%d&quot;, &amp;a[i]);

    // dp运算
    init();
    for (int i = 2; i &lt;= m; ++i)
        L(i);

    // for (int i = 0; i &lt;= m; ++i) {
    //     for (int j = 0; j &lt;= n; ++j)
    //         printf(&quot;%d &quot;, dp[i][j]);
    //     printf(&quot;\n&quot;);
    // }

    //找出最优解
    int ans = -INF;
    for (int i = 1; i &lt;= n; ++i)
        ans = max(ans, dp[m][i]);

    printf(&quot;%d\n&quot;, ans);
}
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

AOJ 901.snow halation