http://tyvj.cn/p/3074
真坑的题目。。核心是求最大子段和，DP搞定
“其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。”
原来前面可以分别找出两个小朋友，一个特征值的最大，一个分数最大
最后两个点还超long long。。
加了取模又莫名WA两个点。。
然后弄了个特判，AC了。。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1000000 + 2; long long a[maxn];//举数 long long f[maxn];//特征值 int main () { int n,p; scanf("%d%d", &n, &p); long long maxh;//前最大特征 long long maxr;//前最大特征值 long long maxf;//前最大分数+特征值 long long ans; //前最大分数 f[0] = -10000000000; bool ghost = false; for (int i=1;i<=n;i++) { scanf("%lld", &a[i]); f[i] = max(f[i-1]+a[i], a[i]); maxr = (i==1) ? (f[i]) :(max(f[i], maxr)); if (ghost) ans = (i==1) ? (f[i]) : maxf; else ans = (i==1) ? (f[i]) : max(maxf,ans); if (ans>1000000000) {ans %= p; ghost = true;} if (ghost) maxf = (i==1) ? (ans+maxr) : maxf+maxr; else maxf = (i==1) ? (ans+maxr) : max(maxf, maxf+maxr); if (maxf>1000000000) {maxf %= p;ghost = true;} } printf("%lld\n", ans%p); return 0; }
