文章

最大和(2022省赛)

最大和1.png最大和2.png

动态规划 下面题解有两个样例超时了。。。。。 方程: a[j]=max(a[i]+num[j],a[j]);

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=2e4+10;
const long long int minn=-2e6+10;
long long int num[maxn];
long long int a[maxn];
long long int check(long long int x){
    long long int i;
    for(i=2;i<sqrt(x)+2&&i<x;i++){
        if(x%i==0) return 0;
    }
    return 1;
}
long long int big(long long int x){
    long long int i;
    if(x==1) return 1;
    for(i=2;;i++){
        if(x%i==0&&check(i)==1){//因数+质数 
            return i; 
        }
    }
}
int main()
{
    long long int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>num[i];
    }
    for(i=1;i<=n;i++){
        a[i]=minn;
    }
    a[1]=num[1];
//  for(i=1;i<=n;i++){
//      cout<<a[i]<<' ';
//  }cout<<endl;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=i+big(n-i)&&j<=n;j++){
            a[j]=max(a[i]+num[j],a[j]);
        }
    }
    cout<<a[n]<<endl;
    return 0;
}
​

原题链接

https://www.lanqiao.cn/problems/2385/learning/

License:  CC BY 4.0