题意：有n棵摇钱树，k天，每天可砍一棵并获得其金币
每棵树初始有$a_i$个金币，每天减少$b_i$个
问k天得到的最多金币数
这题很明显是DP（锻炼自己的机会来了QAQ）
设$f[i][j]$代表前i棵数，到第j天所得最大值
$f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]-(j-1)*b[i])$ 666
但是跑完样例发现
f[3][2]=44
f[3][3]=43!!!
what？？？
咋多了一天答案反而减少了？？
输出DP过程，发现$a[i]-(j-1)*b[i]$可能是负的！！
但实际上一棵树不可能有负数个金币
所以判断若是负数让其等于0
这还不够，f[3][3]=44.......应该是47
假设我们有3棵树且要选全部，每棵价值和每次消耗分别为$m1,m2,m3;b1,b2,b3;$则$总价值=m1+m2+m3-k1*b1-k2*b2-k3*b3$，
很明显我们要选消耗大的啊
所以排序后，47自然就出来了qaq
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double int n; int k; struct node { int num; int down; friend bool operator < (const node &a,const node &b) { return a.down>b.down; } }a[1050]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int f[1050][1050]; signed main() { while(5201314) { n=read(); k=read(); if(!n&&!k) break; memset(f,0,sizeof f); for(int i=1;i<=n;i++) a[i].num=read(); for(int i=1;i<=n;i++) a[i].down=read(); sort(a+1,a+n+1); for(int j=1;j<=k;j++) for(int i=1;i<=n;i++) { int x=a[i].num-(j-1)*a[i].down; x=x>0? x:0; f[i][j]=max(f[i-1][j],f[i-1][j-1]+x); } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,f[n][i]); put(ans); putchar('n'); } olinr ~~(0^_^0)+love_nmr; } /* 3 3 10 20 30 4 5 6 0 0 4 3 20 30 40 50 2 7 6 5 */
转载于:https://www.cnblogs.com/olinr/p/9573734.html
