0

2 つのセットが互いに隣接しない (つまり、2 つのセットの間に少なくとも 1 つの数値がある) ように、N 個の数のシーケンスを最大 K 以下のサイズの連続セットに分割し、すべての要素の合計をセットが最大化されます。

たとえば、シーケンスが 1,2,3,4,5 の場合。3 が間にあるので、セット (1,2) と (4,5) に分割できますが、セット (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 に答える