自动搬运

查看原文

来自洛谷，原作者为

	lkjzyd20 Am I Sunshine Deprimere? I think so.

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

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

以下是正文

思路

很巧妙的 dp，但这题可以贪心（160 行）。

我们很容易思考出来一个贪心，就是把每个货架只留一个最多的面包，但是这样会出现有可能一排都没有可以放的面包。

我们可以通过上面的贪心发现，面包之间是可以互相影响的，所以考虑 dp。

定义 $f_{i,x}$ 表示前 $i$ 个货架已经整理完毕，且第 $i$ 个货架的状态为 $x$（用 $3$ 位二进制表示分别是否存放蛋糕、甜甜圈、羊角面包）。

则

• 如果货架上有蛋糕，就移走甜甜圈和羊角面包。
• 如果货架上有甜甜圈，就移走蛋糕和羊角面包。
• 如果货架上有羊角面包，就移走甜甜圈和蛋糕。

代码实现

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=300010;
int n, d[N], p[N], r[N];
int f[N][8];
int a,b,c;
main() 
{
    cin>>n;
	memset(f,0x3f,sizeof f);
    f[0][0] = 0;
    rep(i,1,n)
    {
    	cin>>d[i]>>p[i]>>r[i];
        if(d[i]) a=4;
        if(p[i]) b=2;
        if(r[i]) c=1;
    }
    rep(i,1,n)
    	rep(x,0,7)
        {
            f[i][x]=1e18;
            if(x&4) f[i][x]=min(f[i][x],min(f[i-1][x],f[i-1][x^4])+p[i]+r[i]);
            if(x&2) f[i][x]=min(f[i][x],min(f[i-1][x],f[i-1][x^2])+d[i]+r[i]);
            if(x&1) f[i][x]=min(f[i][x],min(f[i-1][x],f[i-1][x^1])+d[i]+p[i]);
        }
    cout<<f[n][a+b+c];
    return 0;
}