大连网站哪家做的好免费加客源

题目链接

几乎所有DP题目前本蒟蒻都没有思路。当然包括但不限于这道题。每次都是看了题解然后打的(等价于抄题解)很羞耻

这道题经思考发现，越靠前砍的果树长果子的能力一定越弱，如果长果子的能力一样弱就先把本来果子多的砍下来。这样可以最大程度的榨干果树的潜能(雾)

又因为每天只砍一棵树，所以不知道为什么这题被转化成了一个01背包?

状态转移方程如下：dp[j]=max(dp[j],dp[j-1]+fru[i].a+fru[i].b*(j-1));

当然，因为要先砍长果子能力弱的，所以要排序之后再DP

代码如下

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;const int size=300000;inline long long max(long long a,long long b){    return a>b?a:b;    }inline long long read(){long long num=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')    f=-1;ch=getchar();}while(isdigit(ch)){num=(num<<1)+(num<<3)+ch-'0';ch=getchar();}return num*f;
}struct Tree{int first;int multi;
}que[size];int f[size];bool cmp(Tree a,Tree b){if(a.multi!=b.multi)    return a.multi<b.multi;return a.first<b.first;
}int main(){int n=read(),m=read();for(int i=1;i<=n;++i)    que[i].first=read();for(int i=1;i<=n;++i)    que[i].multi=read();sort(que+1,que+n+1,cmp);for(int i=1;i<=n;++i)for(int v=m;v>=1;--v)f[v]=max(f[v],f[v-1]+que[i].first+que[i].multi*(v-1));printf("%d",f[m]);return 0;
}