简答题 偏难
#7163

吃奶酪 Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线,每块奶酪都有不同的美味程度。然而,如果有相邻两块奶酪都被Jerry偷吃,Tom就会发现这一点并…

吃奶酪

Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线,每块奶酪都有不同的美味程度。然而,如果有相邻两块奶酪都被Jerry偷吃,Tom就会发现这一点并迅速抓住Jerry。Jerry当然希望在不被Tom发现的条件下吃到的奶酪美味度总和最大。当然,他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案,告诉他最多能偷吃到多少的美味度吧。

时间限制:1000

内存限制:65536

输入

第一行一个整数T (T<=100),表示测试数据组数。 接下来,每组测试数据包含两行。其中,第一行一个整数n (1 <= n <= 100,000) ,表示奶酪的数量;第二行n个整数,表示这一排直线上奶酪的美味程度,请注意,美味度保证能够被int类型存储,且可能是负数。

输出

对于每组测试数据,输出一个整数,表示Jerry可以吃到的最大美味度总和。请注意,美味度总和可能超过int存储范围

样例输入

2
4
1 2 3 1
5
2 7 9 3 1

样例输出

4
12
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; long long d[100005]; int a[100005]; int main() {   int t;   cin &gt;&gt; t;   while (t--) {     int n;     memset(d, 0, sizeof(d));     memset(a, 0, sizeof(a));     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++)       cin &gt;&gt; a[i];     d[1] = max(0, a[1]);     d[2] = max(int(d[1]), a[2]);     for (int i = 3; i &lt;= n; i++) {       d[i] = max(d[i - 1], a[i] + d[i - 2]);     }     cout &lt;&lt; d[n] &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。