对于 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; }