原题链接:https://www.luogu.com.cn/problem/P1982
题意解读:
特征值:第i个同学的特征值是1~i中最大子段和,分数:第i个同学分数是前1~i-1个同学的分数+特征值最大值,求最大分数。
解题思路:
第一步:先计算特征值f[i],f[i]等于1~i中所有数的最大子段和,所以借助最大子段和的DP方法,每次计算以i结尾的最大子段和,同时更新1~i为止最大的子段和,f[i] = 当前最大的子段和
第二步:计算分数,枚举所有的同学,计算上一个同学的分数+特征值,并更新最大的分数+特征值,该值为当前同学分数
80代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, p;
long long a[N]; //原数组
long long f[N]; //特征值
int main()
{
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
//计算特征值,f[i]=1~i的最大子段和
f[1] = a[1];
long long maxd = f[1];
long long res = f[1];
for(int i = 2; i <= n; i++)
{
maxd = max(maxd + a[i], a[i]); //计算以i结尾的最大子段和
res = max(res, maxd); //更新1~i之间的最大子段和
f[i] = res;
}
//计算分数
long long maxs = f[1]; //最大分数
long long g = f[1]; //前一个人的分数
long long maxx = f[1] + f[1]; //最大分数+特征值
for(int i = 2; i <= n; i++)
{
maxx = max(maxx, f[i-1] + g);
g = maxx;
maxs = max(maxs, g);
}
cout << maxs % p;
return 0;
}
只能得到80分的原因是,在计算分数的过程中,会对maxx进行n次加法操作,每次加10^15,数据规模达到10^21,会爆long long
因此需要用高精度,只需要用两个元素的long long数组来实现高精度,每一数存18位
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const long long BASE = 1e18;
int n, p;
long long a[N]; //原数组
long long f[N]; //特征值
bool cmp(long long a[2], long long b[2])
{
if(a[1] == b[1]) return a[0] < b[0];
return a[1] < b[1];
}
int main()
{
cin >> n >> p;
for(int i = 1; i <= n; i++) cin >> a[i];
//计算特征值,f[i]=1~i的最大子段和
f[1] = a[1];
long long maxd = f[1];
long long res = f[1];
for(int i = 2; i <= n; i++)
{
maxd = max(maxd + a[i], a[i]); //计算以i结尾的最大子段和
res = max(res, maxd); //更新1~i之间的最大子段和
f[i] = res;
}
//计算分数
long long maxs[2] = {f[1]}; //最大分数
long long g[2] = {f[1]}; //前一个人的分数
long long maxx[2] = {f[1] + f[1]}; //最大分数+特征值
for(int i = 2; i <= n; i++)
{
long long res[2] = {0, 0};
res[0] = f[i-1] + g[0];
res[1] = g[1];
res[1] += res[0] / BASE;
res[0] = res[0] % BASE;
if(cmp(maxx, res)) maxx[1] = res[1], maxx[0] = res[0];
g[1] = maxx[1], g[0] = maxx[0];
if(cmp(maxs, g)) maxs[1] = g[1], maxs[0] = g[0];
}
cout << (maxs[1] % p * (BASE % p) + maxs[0] % p) % p;
return 0;
}
标签:分数,特征值,NOIP2013,最大,子段,int,long,P1982,CSP From: https://www.cnblogs.com/jcwy/p/18229144