猴子(弱)
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[100005]; int f[305][305]; int ma[305]; int main () { int n,d,m; scanf("%d%d%d",&n,&d,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&tr[i].cost,&tr[i].dis); } f[0][1]=tr[1].cost; ma[0]=tr[1].cost; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { int k=j-1; while(tr[j].dis-tr[k].dis<=d&&k>0) { if(i==1&&k==1) f[i][j]=max(f[i][j],f[0][1]+tr[j].cost); else if(f[i-1][k]!=0) { f[i][j]=max(f[i][j],f[i-1][k]+tr[j].cost); } k--; } ma[i]=max(ma[i],f[i][j]); } if(ma[i]==0) { printf("%d\n",ma[i-1]); exit(0); } } int sum=0; for(int i=m;i<=n;i++) { sum=max(sum,f[m][i]); } printf("%d",sum); return 0; }
显然这并不是我想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,-1,sizeof(f)); scanf("%d%d%d",&n,&d,&m); int a=n; for(int i=1;i<=n;i++) { cin>>tree1[i].num>>tree1[i].s; if(tree1[i].s-d>tree1[i-1].s&&a==n) { a=i-1; } } n=a; f[1][0]=tree1[1].num; for(int j=0;j<m;j++) { int h=1,t=1; for(int i=2;i<=n&&tree1[i].s<=d*(j+1);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+1]=max(f[h][j]+(long long)tree1[i].num,f[i][j+1]); } } long long sum=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { sum=max(sum,f[i][j]); } } printf("%lld\n",sum); return 0; }
#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,-1,sizeof(f)); scanf("%d%d%d",&n,&d,&m); int a=n; for(int i=1;i<=n;i++) { cin>>tree1[i].num>>tree1[i].s; if(tree1[i].s-d>tree1[i-1].s&&a==n) { a=i-1; } } n=a; f[1][0]=tree1[1].num; for(int j=0;j<m;j++) { int h=1,t=1; que[1]=f[j+1][j]; memset(b,0,sizeof(b)); b[1]=j+1; for(int i=j+2;i<=n;i++) { if(tree1[i].s>(j+1)*d)break; while(tree1[b[h]].s+d<tree1[i].s&&h<=t) { que[h]=0; h++; } while(que[t]<=f[i-1][j]&&t>=h) { que[t]=0; t--; } b[++t]=i-1; que[t]=f[i-1][j]; f[i][j+1]=que[h]+(long long)tree1[i].num; } } long long sum=0; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { sum=max(sum,f[i][j]); } } printf("%lld\n",sum); return 0; }
嘿嘿嘿，谁有更简单的？