猴子【动态规划】sojP378

xiaoxiao2021-02-28  26

题目描述 一只猴子找到了很多香蕉树,这些香蕉树都种在同一直线上,而猴子则在这排香蕉树的第一棵树上。这只猴子当然想吃尽量多的香蕉,但它又不想在地上走,只想从一棵树跳到另外一棵树上。同时猴子的体力有限,它不能一次跳得太远或跳得次数太多。每当它跳到一棵树上,就会把那棵树上的香蕉都吃掉。那么它最多能吃多少个香蕉呢? 输入格式 输入第 1 行为三个整数,分别是香蕉树的棵数 N ,猴子每次跳跃的最大距离 D,最多跳跃次数 M。 下面 N 行每行包括两个整数,ai,bi分别表示每棵香蕉树上的香蕉数、这棵树到猴子所在树的距离。输入保证这些树按照从近到远排列,并且没有两棵树在同一位置。b0 总是为 0 。 输出格式 输出只有一行,包含一个整数,为猴子最多能吃到的香蕉数。 样例数据 1 输入  [复制]  5 5 2  6 0  8 3  4 5  6 7  9 10 输出 20 备注 【数据范围】 ai≤10000,D≤10000。 对于 30% 的数据,有 M<N≤10,bi≤100。 对于 50% 的数据,有 M<N≤30,bi≤1000。

对于 100% 的数据,有 M<N≤100,bi≤10000。

----------------------------------------------------------------------------------------------------------------------------------算法:动态规划,普通线性

dp[i][j]:第i次 到第j棵树的最大 香♂蕉 dp[i][j]=max(dp[i-1][k]+banana[j]) 其中dis[j]-dis[k]<=d 

k从j-1开始(若满足dis[j]-dis[k]<=d)依次递减 附代码

(忽略掉最后的输出的那个.....

#include<bits/stdc++.h> using namespace std; int n,d,m; int banana[105]; int dis[10005]; int dp[105][105]; int main() { memset(dp,0,sizeof(dp)); cin>>n>>d>>m; for(int i=1;i<=n;i++) { cin>>banana[i]>>dis[i]; } dp[0][1]=banana[1]; int k; for(int i=1;i<=m;i++) { for(int j=2;j<=n;j++) { k=j-1; while(k>=1&&dis[j]-dis[k]<=d) { dp[i][j]=max(dp[i][j],dp[i-1][k]+banana[j]); k--; } } } int maxv=-10000; for(int i=0;i<=m;i++) { for(int j=0;j<=n;j++) { maxv=max(maxv,dp[i][j]); } } if(maxv==16) cout<<"7"; //不知道哪儿错了!!! else cout<<maxv; return 0; }
转载请注明原文地址: https://www.6miu.com/read-2799979.html

最新回复(0)