题目传送门

这篇题解主要讲解状态转移方程是怎么来的，其他的题解都仅仅将状态转移方程写出来。

变量名称定义

$a_{i}$ 第 $i$ 个物品的金额。
$dp_{i}$ 购买前 $i$ 个物品所需的最少金额。
$n,q$ 同题目意思。

状态转移方程

显然只能将账单分为若干个一件和三件。

• 三件以上的，分开可以多优惠一次
• 两件的等价于两个一件

先看 $i<3$ 的情况。此时只能选择第二种优惠方法，无奈之举：

$$dp_{i}=dp_{i-1}+a_{i}\times(1-q\%)$$

易错点就是把 $dp_{i-1}$ 也乘上折扣。实际上，在上一轮循环中，已经打过折了。

$i\ge3$ 时，若选择第一种优惠方式（即拆分为前 $i-3$ 件和三件），则有：

$$dp_{i}=dp_{i-3}+a_{i-1}+a_{i-2}$$

其中 $a_{i}$ 被免费掉了。
若选择第二种优惠方式，则有：

$$dp_{i}=dp_{i-1}+a_{i}\times (1-q\%)$$

选两种方案中最佳的即可，故：

$$dp_{i}=\min(dp_{i-3}+a_{i-1}+a_{i-2},\ dp_{i-1}+a_{i}\times (1-q\%))$$

处理细节

状态转移方程中，我们默认免费掉了 $a_{i}$，故需要先降序排序。

$dp_{0}=0$。

代码

#include <bits/stdc++.h>
using namespace std;

int n,q,a[100005];
long long dp[100005];

bool cmp(int x, int y)
{return x>y;}

int main()
{
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
	scanf("%d %d",&n,&q);
	for (int i=1; i<=n; i++)
	{
	    scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1,cmp);
	for (int i=1; i<=n; i++)
	{
	    if (i<3)
	    {
	        dp[i]=dp[i-1]+a[i]*(100-q)/100;
	        continue;
	    }
	    dp[i]=min(dp[i-3]+a[i-2]+a[i-1],dp[i-1]+a[i]*(100-q)/100);
	}
	printf("%lld",dp[n]);
	return 0;
}

题外话

写完了才发现题目对商品价格变量有规定了，是 $p_{i}$，不过无所谓好吧。