题面 https://www.luogu.org/problem/P1417
这道题是一道典型的排序 dp
a[i]−b[i](t+c[i])+a[j]−b[j](t+c[i]+c[j])
a[j]−b[j](t+c[j])+a[i]−b[i](t+c[i]+c[j])a[j]-b[j]*(t+c[j])+a[i]-b[i]*(t+c[i]+c[j])a[j]−b[j](t+c[j])+a[i]−b[i](t+c[i]+c[j])
a[i]−b[i](t+c[i])+a[j]−b[j](t+c[i]+c[j])>a[j]−b[j](t+c[j])+a[i]−b[i](t+c[i]+c[j])a[i]-b[i]*(t+c[i])+a[j]-b[j]*(t+c[i]+c[j])>a[j]-b[j]*(t+c[j])+a[i]-b[i]*(t+c[i]+c[j])a[i]−b[i](t+c[i])+a[j]−b[j](t+c[i]+c[j])>a[j]−b[j](t+c[j])+a[i]−b[i](t+c[i]+c[j])
−b[i](t+c[i])−b[j](t+c[i]+c[j])>−b[j](t+c[j])−b[i](t+c[i]+c[j])-b[i]*(t+c[i])-b[j]*(t+c[i]+c[j])>-b[j]*(t+c[j])-b[i]*(t+c[i]+c[j])−b[i](t+c[i])−b[j](t+c[i]+c[j])>−b[j](t+c[j])−b[i](t+c[i]+c[j])
−b[i]t−b[i]c[i]−b[j]t−b[j]c[i]−b[j]c[j]>−b[j]t−b[j]c[j]−b[i]t−b[i]c[i]−b[i]c[j]-b[i]*t-b[i]*c[i]-b[j]*t-b[j]*c[i]-b[j]*c[j]>-b[j]*t-b[j]*c[j]-b[i]*t-b[i]*c[i]-b[i]*c[j]−b[i]t−b[i]c[i]−b[j]t−b[j]c[i]−b[j]c[j]>−b[j]t−b[j]c[j]−b[i]t−b[i]c[i]−b[i]c[j]
−b[j]c[i]>−b[i]c[j]-b[j]*c[i]>-b[i]*c[j]−b[j]c[i]>−b[i]c[j]
所以最后按−b[j]c[i]>−b[i]c[j]-b[j]*c[i]>-b[i]*c[j]−b[j]c[i]>−b[i]c[j] 的规则进行排序就行了
- #include <bits/stdc++.h>
- using namespace std;
- int n,t;
- struct haha{
- int a;
- int b;
- int c;
- }a[100000];
- int f[100000];
- bool cmp(haha i,haha j){
- return -j.b*i.c>-i.b*j.c;
- }
- int main(){
- int ans=0;
- scanf("%d%d",&t,&n);
- for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
- for(int i=1;i<=n;i++) scanf("%d",&a[i].b);
- for(int i=1;i<=n;i++) scanf("%d",&a[i].c);
- sort(a+1,a+n+1,cmp);
- for(int i=1;i<=n;i++){
- for(int j=t;j>=a[i].c;j--){
- f[j]=max(f[j],f[j-a[i].c]+a[i].a-a[i].b*j);
- ans=max(ans,f[j]);
- }
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3198912.html