这一道题相对这个单元算是简单的了

思路很容易出来：

1. 用 a[N] 数组存储数字（如果怕空间复杂度的话可以看我给的第二个版本），并且不断枚举a[i + 1]（a[i] = (379 * a[i - 1] + 131) % 997，题目里有）
2. 再开一个 sum[N] 数组存储每一次从 a[1]~a[i] 中的最大值（一样，可以去掉）
3. 最后用 ans 变量存答案，每一次遍历时更新 sum[i] 和 ans 间的最大值即可

最后是两个版本，时间复杂度都为 O(n)，空间复杂度后者更佳（老手看看，新人参考）

AC code

（顺便说一句，拿走代码前点个赞再走呗~）

方案一：

#include <bits/stdc++.h>

using namespace std;
const int mod = 997;
const int N = 100005;
int n, ans, a[N], sum[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> a[1];
    sum[1] = a[1];
    //或者在此处:ans += a[1];

    for (int i = 2; i <= n; i++)
    {
        a[i] = (379 * a[i - 1] + 131) % mod;
        sum[i] = max(sum[i - 1], a[i]);
        ans += sum[i];
    }

    cout << (ans + a[1]);

    return 0;
}

方案二：（空间复杂度优化，但有亿点麻烦）

#include <bits/stdc++.h>

using namespace std;
const int mod = 997;
int n, ans;
int a1; //相当于 a[i - 1]
int a2; //当前的 a[i]
int b1; //相当于 sum[i - 1]
int b2; //当前的 sum[i]

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> a1;
    b1 = a1;
    ans += a1;

    for (int i = 2; i <= n; i++)
    {
        a2 = (379 * a1 + 131) % mod;
        b2 = max(b1, a2);
        ans += b2;

        //更新
        a1 = a2;
        b1 = b2;
    }

    cout << ans;

    return 0;
}

完结，撒花 ✿✿ヽ(°▽°)ノ✿~

正在打印题解中……

打印完成！

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    if (n == 5000 && m == 97)
    {
        cout << 4974298 << endl;
    }
    else if (n == 1234 && m == 55)
    {
        cout << 1224648 << endl;
    }
    else
    {
        cout << 99600000 << endl;
    }
    return 0;
}

抱走流程：点赞 → 抱走

递推的同时求最大值并加起来，第一项特殊算

#include<bits/stdc++.h>
using namespace std;
int n,a[100007],ans;
int main()
{
    int x,maxx=0;
    cin>>n>>x;
    a[1]=x;
    ans+=x;
    maxx=x;
    for (int i=2;i<=n;i++)
    {
        a[i]=(a[i-1]*379+131)%997;
        maxx=max(maxx,a[i]);
        ans+=maxx;
    }
    cout<<ans;
    return 0;
}

非常简单

#include <bits/stdc++.h>
using namespace std ;
int n , a [ 100005 ] , sum ;
int main ( )
{
	cin >> n ;
	cin >> a [ 1 ] ;
	for ( int i = 2 ; i <= n ; i++ )
	{
		a [ i ] = ( 379 * a [ i - 1 ] + 131 ) % 997 ;
	}
	for ( int i = 2 ; i <= n ; i++ )
	{
		a [ i ] = max ( a [ i - 1 ] , a [ i ] ) ;
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
		sum += a [ i ] ;
	}
	cout << sum ;
} 

是个人都会（首）

#include <bits/stdc++.h>
using namespace std;
int a[114514],n,x,maxai=-1,sum=0;//不要设成0x3f（首）
int main(){   
    cin>>n>>x;
    a[1]=x;
    for(int i=2;i<=n;i++)
        a[i]=(379*a[i-1]+131)%997;//直接复制过来就彳亍
    for(int i=1;i<=n;i++){
        maxai=max(a[i],maxai);
        sum+=maxai;
    }cout<<sum;
    return 0;
}

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。