题外话：
由于昨天考DP专题考到怀疑人生
所以今天决定刷刷基础题
先把洛谷普及练习场的DP写掉
思路：
知道它是一个DP题 但是看到题目有一点点懵
因为物品的价值还和取的时间有关
仔细想想 发现这题可能有点像国王游戏
要找一找规律 用式子推一下
如下：
1.a[i]-(t+c[i])*b[i]+a[j]-(t+c[i]+c[j])*b[j] >
a[j]-(t+c[j])*b[j]+a[i]-(t+c[j]+c[i])*b[i]
2. a[i]-t*b[i]-c[i]*b[i]+a[j]-t*b[j]-c[i]*b[j]-c[j]*b[j] >
a[j]-t*b[j]-c[j]*b[j]+a[i]-t*b[i]-c[j]*b[i]-c[i]*b[i]
3.c[i]*b[j]<c[j]*b[i]
可知 若c[i]*b[j]<c[j]*b[i] 则先取 i 获得的价值大一些
所以我们就可以由此先排个序 然后一般的01背包就可以啦
小结：
求最值的问题可以想想DP
然后题目里有一些式子的时候可以考虑推结论找规律来简化题目
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define ll long long 5 #define go(i,a,b) for(register int i=a;i<=b;i++) 6 #define yes(i,a,b) for(register int i=a;i>=b;i--) 7 #define M 100010 8 using namespace std; 9 int read() 10 { 11 int x=0,y=1;char c=getchar(); 12 while(c<‘0‘||c>‘9‘) {if(c==‘-‘) y=-1;c=getchar();} 13 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} 14 return x*y; 15 } 16 struct node {ll a,b,c;} d[M]; 17 int T,n; 18 ll f[M],ans; 19 bool cmp(node x,node y) {return x.c*y.b<y.c*x.b;} 20 int main() 21 { 22 T=read();n=read(); 23 go(i,1,n) d[i].a=read(); 24 go(i,1,n) d[i].b=read(); 25 go(i,1,n) d[i].c=read(); 26 sort(d+1,d+n+1,cmp); 27 go(i,1,n) 28 yes(j,T,d[i].c) 29 f[j]=max(f[j],f[j-d[i].c]+d[i].a-j*d[i].b); 30 go(i,1,T) ans=max(ans,f[i]); 31 printf("%lld",ans); 32 return 0; 33 }
原文：https://www.cnblogs.com/forward777/p/10325020.html
