Loading...

洛谷P1417 烹调方案

check评论:0 条 remove_red_eye浏览量:146 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-06-25

我动规太差了啊...qaq,先把多项式放放吧

题目链接

  • 题目描述

一共有n件食材,每件食材有三个属性,$a_i$,$b_i$和$c_i$,如果在$t$时刻完成第$i$样食材则得到$a_i-t\times b_i$的美味指数,用第i件食材做饭要花去$c_i$的时间,需要在$T$时间内做出最美味的食物,请设计烹调方案使得美味指数最大并输出

  • 题目分析

$T$时间内取部分东西使得其有最大值,很明显是个$01$背包,但是由于时间会改变美味结果导致此时有后效性,无法动规。

考虑各个物品的优先值,物品$1$和物品$2$,如果先做$1$再$2$比先做$2$再$1$更好,则$a1+a2-b1c1-b2c2-b1c2>a1+a2-b1c1-b2c2-b2c1$,即$b2c1>b1c2$

故以此为关键字排序,然后$01$背包即可

  • 代码实现
/**************************/
/*It is made by decoration*/
/*gzzkal   gzzkal   gzzkal*/
/*It is made by decoration*/
/**************************/
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    int a,b,c;
    bool operator<(const node&a)const
    {
        return a.c*b>c*a.b;
    }
}no[210];
int dp[100100];
main()
{
    int t,n;
    cin>>t>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>no[i].a;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>no[i].b;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>no[i].c;
    }
    sort(no+1,no+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=t;j>=no[i].c;j--)
        {
            dp[j]=max(dp[j],dp[j-no[i].c]+no[i].a-no[i].b*j);
        }
    }
    cout<<*max_element(dp+1,dp+t+1);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名