题解：P9294 [POI 2020] Cukiernia / 糕点店

lkjzyd20 · 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;
}