洛谷 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[];

int f[];

bool cmp(haha i,haha j){

    return -j.b*i.c>-i.b*j.c;

}

int main(){

       int ans=;

    scanf("%d%d",&t,&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i].a);

    for(int i=;i<=n;i++) scanf("%d",&a[i].b);

    for(int i=;i<=n;i++) scanf("%d",&a[i].c);

    sort(a+,a+n+,cmp);

    for(int i=;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 ;

}

巴特西

洛谷 P1417 烹调方案题解

最新文章

热门文章

巴特西

洛谷 P1417 烹调方案 题解

最新文章

热门文章

洛谷 P1417 烹调方案题解