【动规递推】聪明伶俐的香穗子

聪明伶俐的香穗子

香穗子遇到难题了.

题目是这样的,一个序列上有n个整数,现在你要取m个,且这m个数的任意两个不能相隔的太近,否则这样会太丑,现在问你最大能得到多大的和

输入:

第一行三个数n,m,k,分别表示n个数,取m个,且m个中的任意两个位置差要大于等于K

接下来一行,有n个整数,表示序列上的每个数

输出:

最大和

Sample Input

4 2 2

3 4 -5 1

Sample Output

数据范围:

n<=10000,m<=100，m<=n

答案保正小于 Maxlongint

这一题用f[i][j]表示前 i 个数中取 j 个数所能得到的最大值

那么就可以得到递归方程

f[i][j]= max{ (取) f[i-k][j-1]+a[i],

(不取) f[i-1][j] }

在样例数据中可以看出数据有负数，所以要赋初值，全部 -INF

然后由于要用到j-1，所以一个预处理算出所有f[i][0]=0

推的时候已经有了f[i][0]，所以 j 从1开始推

C++ Code

/*
C++ Code
http://oijzh.cnblogs.com
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXM 110
#define MAXN 10010
#define INF 0x7fffffff

int n,m,k,a[MAXN],f[MAXN][MAXM];//f[已经取了几个数][当前位置]

int main()
{
    freopen("4.in","r",stdin);
    freopen("4.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    int i,j;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,128,sizeof(f));
    for(i=0;i<=n;i++)f[i][0]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(i>=k)f[i][j]>?=f[i-k][j-1]+a[i];
            if(j==1)f[i][j]>?=f[i-1][j-1]+a[i];//j=1时就没有相隔k的限制，可以直接取
        }
    int max=-INF;
    for(i=0;i<=n;i++) max>?=f[i][m];
    printf("%d",max);
    return 0;
}

【动规递推】聪明伶俐的香穗子

原文链接: https://www.cnblogs.com/oijzh/archive/2012/10/14/2723385.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/65756

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

【动规递推】聪明伶俐的香穗子

相关推荐