猴子(弱)
Description
话说NP做梦，梦见自己变成了一只猴子，并且有很多香蕉树，这些香蕉树都种在同一直线上，而NP则在这排香蕉树的第一棵树上。NP当然想吃尽量多的香蕉，但它又不想在地上走，而只想从一棵树跳到另一棵树上。同时NP的体力也有限，它不能一次跳得太远或跳的次数太多。每当他跳到一棵树上，它就会把那棵树上的香蕉都吃了。那么它最多能吃多少香蕉呢？
Input
输入第一行为三个正整数，分别是香蕉树的棵数N，NP每次跳跃的最大距离D，最多跳跃次数M。
下面N行每行包含两个整数，ai，bi，分别表示每棵香蕉树上的香蕉数，以及这棵树到第一棵树的距离。输入保证这些树按照从近到远排列，并且没有两棵树在同一位置。b0总是为0。
ai<=10000,bi<=10000，D<=10000 ，0<M<N<=300
Output
输出只有一行，包含一个整数，为猴子最多能吃到的香蕉数。
Sample Input
Sample Output
#include<cstdio>
#include<algorithm>
using namespace std;
struct tree
{
int cost;
int dis;
int cnt;
}tr[];
int f[][];
int ma[];
int main ()
{
int n,d,m;
scanf("%d%d%d",&n,&d,&m);
for(int i=;i<=n;i++)
{
scanf("%d%d",&tr[i].cost,&tr[i].dis);
}
f[][]=tr[].cost;
ma[]=tr[].cost;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
int k=j-;
while(tr[j].dis-tr[k].dis<=d&&k>)
{
if(i==&&k==) f[i][j]=max(f[i][j],f[][]+tr[j].cost);
else if(f[i-][k]!=)
{
f[i][j]=max(f[i][j],f[i-][k]+tr[j].cost);
}
k--;
}
ma[i]=max(ma[i],f[i][j]);
}
if(ma[i]==)
{
printf("%d\n",ma[i-]);
exit();
}
}
int sum=;
for(int i=m;i<=n;i++)
{
sum=max(sum,f[m][i]);
}
printf("%d",sum);
return ;
}
显然这并不是我想A的题
猴子
Description
一个猴子找到了很多香蕉树，这些香蕉树都种在同一直线上，而猴子则在这排香蕉树的第一棵树上。这个猴子当然想吃尽量多的香蕉，但它又不想在地上走，而只想从一棵树跳到另一棵树上。同时猴子的体力也有限，它不能一次跳得太远或跳的次数太多。每当他跳到一棵树上，它就会把那棵树上的香蕉都吃了。那么它最多能吃多少个香蕉呢？
Input
输入第一行为三个整数，分别是香蕉树的棵数N，猴子每次跳跃的最大距离D，最多跳跃次数M。 下面N行每行包含两个整数，ai，bi，分别表示每棵香蕉树上的香蕉数，以及这棵树到猴子所在树的距离。输入保证这些树按照从近到远排列，并且没有两棵树在同一位置。b0总是为0。
Output
输出只有一行，包含一个整数，为猴子最多能吃到的香蕉数。
Sample Input
Sample Output
HINT
【数据范围】 ai<=10000,D<=10000 100%的数据有M<N<=2000,bi<=10000
这个才是卡了我很久的
其实也没什么，就是简单的单调队列优化DP
我发现了两种优化方法
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define N 2001
int n,d,m,ans;
struct node
{
int s;
int num;
}tree1[N];
long long f[N][N],b[N];
int main()
{
//freopen("tt.in","r",stdin);
//freopen("me.out","w",stdout);
memset(f,-,sizeof(f));
scanf("%d%d%d",&n,&d,&m);
int a=n;
for(int i=;i<=n;i++)
{
cin>>tree1[i].num>>tree1[i].s;
if(tree1[i].s-d>tree1[i-].s&&a==n)
{
a=i-;
}
}
n=a;
f[][]=tree1[].num;
for(int j=;j<m;j++)
{
int h=,t=;
for(int i=;i<=n&&tree1[i].s<=d*(j+);i++)
{
while(tree1[h].s+d<tree1[i].s)
{
h++;
}
while(f[h][j]<f[t][j])
{
h++;
}
t++;
//b[++t]=h;
f[i][j+]=max(f[h][j]+(long long)tree1[i].num,f[i][j+]);
}
}
long long sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
sum=max(sum,f[i][j]);
}
}
printf("%lld\n",sum);
return ;
}
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define N 2001
int n,d,m,ans;
struct node
{
int s;
int num;
}tree1[N];
long long f[N][N],b[N],que[N];
int main()
{
//freopen("tt.in","r",stdin);
//freopen("me.out","w",stdout);
memset(f,-,sizeof(f));
scanf("%d%d%d",&n,&d,&m);
int a=n;
for(int i=;i<=n;i++)
{
cin>>tree1[i].num>>tree1[i].s;
if(tree1[i].s-d>tree1[i-].s&&a==n)
{
a=i-;
}
}
n=a;
f[][]=tree1[].num;
for(int j=;j<m;j++)
{
int h=,t=;
que[]=f[j+][j];
memset(b,,sizeof(b));
b[]=j+;
for(int i=j+;i<=n;i++)
{
if(tree1[i].s>(j+)*d)break;
while(tree1[b[h]].s+d<tree1[i].s&&h<=t)
{
que[h]=;
h++;
}
while(que[t]<=f[i-][j]&&t>=h)
{
que[t]=;
t--;
}
b[++t]=i-;
que[t]=f[i-][j];
f[i][j+]=que[h]+(long long)tree1[i].num;
}
}
long long sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
sum=max(sum,f[i][j]);
}
}
printf("%lld\n",sum);
return ;
}
嘿嘿嘿，谁有更简单的？