牛客，选择23976

Question

https://ac.nowcoder.com/acm/problem/23976

想问问大家我的解题哪里错了啊，我的思路是：对于每一组求每个数与他后面最大数的和，然后将这些和比较选最大的输出

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N];
int main()
{
    int T;
    cin>>T;
    while(T)
    {
        T--;
        int n,m,ans=0;
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int i=0;i<n;i++)
        {m=0;
            for(int j=i+2;j<n;j++)
               if(m<a[j]) m=a[j];
            ans=max(ans,a[i]+m);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Answer 1

思路是对的，但是在计算后面最大数的时候存在一些问题。具体来说，题目要求选出的数不能相邻，而你在计算后面最大数的时候没有考虑到这一点，直接取了后面未选的最大数，可能会导致后面选了不合法的数。

一个正确的方法是记录两个状态，即当前位置选和不选能获得的最大值，然后向后推进时分别计算选和不选的情况下能获得的最大值，并更新这两个状态。最终的答案为所有位置选和不选能获得的最大值中的较大值。

修改代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N];
int f[N][2]; //f[i][0/1]表示考虑到第i个位置时，不选/选第i个位置能获得的最大值
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n, ans = 0;
        cin>>n;
        for(int i=1; i<=n; i++) {
            cin>>a[i];
        }
        memset(f, 0, sizeof(f)); //初始化
        f[1][0] = 0; f[1][1] = a[1];
        for(int i=2; i<=n; i++) {
            f[i][0] = max(f[i-1][0], f[i-1][1]); //不选第i个位置
            f[i][1] = f[i-1][0] + a[i]; //选第i个位置
        }
        ans = max(f[n][0], f[n][1]); //取较大值作为答案
        cout << ans << endl;
    }
    return 0;
}