0

将 N 个数的序列划分为最大为 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;
}
4

1 回答 1

0

既然这听起来像家庭作业，我只会给你一个线索。使用具有函数的动态规划： F(x,i,k) 其中 x 是序列，您正在考虑前 i 个元素，k 是不相交子序列的数量。

于 2012-04-04T16:59:14.203 回答