N个整数组成的序列a[1],a[2],a[3],…,a[n],将这N个数划分为互不相交的M个子段,并且这M个子段的和是最大的。如果M >= N个数中正数的个数,那么输出所有正数的和。
例如: -2 11 -4 13 -5 6 -2,分为2段,11 -4 13一段,6一段,和为26。
Input
第1行:2个数N和M,中间用空格分隔。N为整数的个数,M为划分为多少段。(2 <= N , M <= 5000)第2 - N+1行:N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和
Input示例
7 2-211-413-56-2
Output示例
26 【分析】dp[j][i]表示从1~i分成j份获得的最大值。
#include#define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_back#define mp make_pair#define rep(i,l,r) for(int i=(l);i<=(r);++i)#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int N = 1e6+5;;const int M = 17;const int mod = 1e9+7;const int mo=123;const double pi= acos(-1.0);typedef pair pii;int n,m;int a[N];ll dp[2][N];int main(){ scanf("%d%d",&n,&m); met(dp,0); ll sum=0; int cnt=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]>0)sum+=a[i],cnt++; } if(m>=cnt)return 0*printf("%lld\n",sum); int now=0; for(int i=1;i<=m;i++){ ll mx=dp[now^1][i-1]; dp[now][i]=mx+a[i]; for(int j=i+1;j<=n-m+i;j++){ mx=max(mx,dp[now^1][j-1]); dp[now][j]=max(mx,dp[now][j-1])+a[j]; } now^=1; } now^=1; ll ans=-99999999999999; for(int i=m;i<=n;i++)ans=max(ans,dp[now][i]); printf("%lld\n",ans); return 0;}