將一個序列劃分成連續的最大尺寸集合K

將一個N個數字的序列分成連續的大小至多爲K的集合，使得沒有兩個集合是彼此相鄰的（即至少有一個數字介於兩組），並且所有組中所有元素的總和得到最大化。將一個序列劃分成連續的最大尺寸集合K

例如，如果序列是1,2,3,4,5。我們可以將它分成集合（1,2）和（4,5），因爲3是在它們之間，但不是集合（2,3）和（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; 
}

來源

2012-04-04 i_code

這有點聞起來像功課... – 2012-04-04 15:20:18

這不是一個家庭作業，但只是自我實踐...... – 2012-04-04 19:33:41

因爲它聽起來像功課，我只是給你一個線索。使用函數動態規劃：F（x，i，k）其中x是序列，您首先考慮i個元素，k是不相交子序列的數目。

來源

2012-04-04 16:59:14 ElKamina

將一個序列劃分成連續的最大尺寸集合K

回答

相關問題