시퀀스를 최대 크기의 연속 세트로 나눕니다. K

Question

N 개의 숫자 시퀀스를 최대 K 개의 연속 세트로 나누어 두 세트가 서로 인접하지 않도록합니다 (즉, 중간에 하나 이상의 숫자가 있음). 두 세트) 모든 세트의 모든 요소의 합이 최대가됩니다.

예 : 시퀀스가 ​​1,2,3,4,5 인 경우. 3을 그 (것)들 사이에두고 집합 (2,3)과 (4,5)로하지 않기 때문에 그것을 집합 (1,2)와 (4,5)로 나눌 수 있습니다.

나는 O (NK)를 수행했다. 더 나은 알고리즘을 제안하십시오.

저는 역 추적으로 동적 프로그래밍을 이미 사용했습니다. 내 코드는 다음과 같습니다

#include<cstdio> 
using namespace std; 

long long int max(long long int a,long long int b){ 
    if(a>b) return a; 
    else return b; 
} 

int main(){ 
    int n,k; 
    int p[100000]; 
    long long int v[100001]; 
    scanf("%d %d",&n,&k); 
    int i,j; 
    for(i=0;i<n;i++) 
     scanf("%d",&p[i]); 
    v[0]=0; 
    v[1]=p[n-1]; 
    int l=1; 
    for(i=n-2;i>-1;i--){ 
     long long int temp=v[l]; 
     l=(n-i)>k?k:(n-i); 
     int m=(k-i)>1?(k-i):1; 
     for(j=l;j>=m;j--) 
      v[j]=max(p[i]+v[j-1],temp); 
     v[0]=temp; 
    } 
    printf("%lld\n",v[k]); 
    return 0; 
} 

Answer 1

는 숙제 같은 소리 때문에, 나는 당신에게 단서를 제공 할 것입니다. 함수로 동적 프로그래밍 사용 : F (x, i, k) 여기서 x는 시퀀스이고 첫 번째 요소는 고려하고 k는 분리 된 하위 시퀀스의 수입니다.