自动搬运

查看原文

来自洛谷，原作者为

	qwerty12346 这个家伙很懒，什么也没有留下(互关)

搬运于2025-08-24 22:47:15，当前版本为作者最后更新于2023-05-30 16:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

就是求海蒂她买所有 $n$ 件商品至少需要多少钱。

思路

直接动态规划递推每次的最小值，并从大到小排序物品的价钱。

状态定义

$dp_{i}$ 表示在第 $i$ 个物品时的最小的价钱。

状态转移方程

$dp_{i}=\max(dp_{i-1}+a_{i}×(1-m\%),dp_{i-3}+a_{i-2}+a_{i-1})$

边界定义

将 $dp_{0}$ 定义为 $0$。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],f[100005];//定义dp数组
bool cmp(int x,int y){//将排序变为从大到小
    return x>y;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1,cmp);//排序
    memset(f,INT_MAX,sizeof(f));
    f[0]=0;//边界定义
    for(int i=1;i<=n;i++)
    {
        if(i<3)f[i]=f[i-1]+a[i]/100*(100-m);//判断
        else f[i]=min(f[i-1]+a[i]/100*(100-m),f[i-3]+a[i-2]+a[i-1]);//找最小值
    }
    cout<<f[n]<<endl;
    return 0;
}