时间戳

首页 > 技术文章 > 猴子

猴子

contestant 2013-08-15 23:34 原文

Problem Description

一只猴子找到了很多香蕉树，这些香蕉树都种在同一直线上，而猴子则在这排香蕉树的第一棵树上。这只猴子当然想吃尽量多的香蕉，但它又不想在地上走，只想从一棵树跳到另外一棵树上。同时猴子的体力有限，它不能一次跳到太远或跳得次数太多。每当它跳到一棵树上，就会把那棵树上的香蕉都吃掉。那么它最多能吃多少个香蕉呢？

Input

输入的第1行为三个整数，分别是香蕉树的棵树N，猴子每次跳跃的最大距离D，最多跳跃次数M。（M<=N<=100,D<=10000)
下面N行每行包括两个整数，ai，bi(ai<=10000,bi<=10000)分别表示每棵香蕉树上的香蕉数，以及这棵树到猴子所在树的距离。输入保证这些树按照从近到远排列，并且没有两棵树在同一位置。b0总是为0。

Output

对于每个输入输出包含一个整数为猴子最多能吃到的香蕉数。

Sample Input

5 5 2
6 0
8 3
4 5
6 7
9 10

Sample Output

20
#include <string.h>
#include <stdio.h>

int a[105],b[105];
int dp[105][105];
int sum;

int main()
{
    int n,d,m;
    int i,j,k;
    while(~scanf("%d %d %d",&n,&d,&m))
    {
        memset(dp,0,sizeof(dp));
        for(i=0; i<n; i++) scanf("%d %d",&a[i],&b[i]);
        sum=a[0];
        if(m>0)
            for(i=1; i<n; i++)//1步
            {
                if(b[i]<=d) dp[i][1]=a[0]+a[i];
                else break;
                if(sum<dp[i][1]) sum=dp[i][1];
            }

        for(k=2; k<=m; k++)//大于1步时
            for(i=k-1; i<n-1; i++)//从i棵跳到第j棵树
                for(j=i+1; j<n; j++)//dp[j][k]表示到达第j棵树时走了k步
                    if(b[j]-b[i]<=d && dp[j][k]<dp[i][k-1]+a[j] &&dp[i][k-1]>0)
                    {
                        dp[j][k]=dp[i][k-1]+a[j];
                        if(sum<dp[j][k]) sum=dp[j][k];
                    }
        printf("%d\n",sum);
    }

    return 0;
}
DP

 

推荐阅读