Luogu P2224 [HNOI2001]产品加工题解

这是一道神奇的进程 DP，状态较难确定~~根据其他题解可知要以答案为状态~~

一、分析状态：

先看看有哪些状态：

执行第 $i$ 个任务
A 机器做的时间 $j$
B 机器做的时间 $k$

没了

二、设计最简单的 DP 方案

考虑一个 naive 的暴力：

设三维 bool 数组 $dp[i][j][k]$ 表示执行第 $i$ 个任务时，A 已经做了 $j$ 时，B 已经做了 $k$ 时的状态是否存在

初始时除了 $dp[0][0][0]=1$ ，其他都是 0

显然有

dp[i][j][k]=dp[i-1][j-t_1[i]\ ][k]\operatorname{or}dp[i-1][j][k-t_2[i]\ ]\operatorname{or}dp[i-1][j-t_3[i]\ ][k-t_3[i]\ ]

其中 $dp[i-1][j-t_1[i]\ ][k]$ 表示单独交给 A， $dp[i-1][j][k-t_2[i]\ ]$ 表示单独交给 B， $dp[i-1][j-t_3][k-t_3[i]\ ]$ 表示 AB 合作

复杂度已经 $\Theta(n^3)$ 了，妥妥的 TMLE

三、降维优化

对上述 naive 暴力进行优化

大胆改造： $dp[i][j]=k$ ，即执行第 $i$ 个任务时，A 已经做了 $j$ 时，B 做的最小时间 $k$

一个很显然的贪心：A、B 都应当连续做，这样总时间才最短

初始值：

因为要求最小值，所以 $dp[][]\leftarrow + \infty$ ，又因为当执行第 0 个任务，A 做了 0 时，B 最小做 0 时，所以有 $dp[0][0]\leftarrow 0$

状态转移方程： $dp[i][j]=\min\{dp[i-1][j-t_1[i]\ ],dp[i-1][j]+t_2[i],dp[i-1][j-t_3[i]\ ]+t_3[i]\}$

三项分别表示单独交给 A，单独交给 B，AB 合作，注意考虑是否能取到的问题，三项能取到的条件分别为 $t_1[i]\not=0,j>t_1[i]$ ， $t_2[i]\not=0$ ， $t_3[i]\not=0,j>t_3[i]$

最终答案即 $\min\limits_{i=1}^{maxt}\{\max\{i,dp[n][i]\}\}$

其中 $maxt=\sum\limits_{i=1}^n\max\{t_1[i],t_2[i],t_3[i]\}$

四、时空优化

这样依然会 MLE，考虑使用滚动数组

因为 $dp[i][]$ 仅由 $dp[i-1][]$ 推得，所以可以压掉这一维

原式即为 $dp[i\operatorname{and}1][j]=\min\{dp[i\operatorname{and}1\operatorname{xor}1][j-t_1[i]\ ],dp[i\operatorname{and}1\operatorname{xor}1][j]+t_2[i],dp[i\operatorname{and}1\operatorname{xor}1][j-t_3[i]\ ]+t_3[i]\}$ ，仍需考虑是否能取到

直接吃掉一维，但注意 $dp$ 数组的第二维最大值得开到 $n\times t$ ，即 $3\times10^4$

细节比较多，所以...

五、代码

#include <bits/stdc++.h>
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=3e4+10;//注意数组大小
int dp[2][N],ans=0x3f3f3f3f,maxt;
signed main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    memset(dp,0x3f,sizeof(dp));//初始化
    dp[0][0]=0;
    rep(i,1,n){
        memset(dp[i&1],0x3f,sizeof(dp[i&1]));//注意这里要再初始化一次！
        int x,y,z;cin>>x>>y>>z;maxt+=max(x,max(y,z));//省掉一个数组了
        rep(j,0,maxt){
            if(y)dp[i&1][j]=min(dp[i&1][j],dp[i&1^1][j]+y);
            if(x&&j>=x)dp[i&1][j]=min(dp[i&1][j],dp[i&1^1][j-x]);
            if(z&&j>=z)dp[i&1][j]=min(dp[i&1][j],dp[i&1^1][j-z]+z);//状态转移方程
        }
    }
    rep(i,0,maxt)ans=min(ans,max(i,dp[n&1][i]));
    cout<<ans;
}

六、总结

一道相当有趣且毒瘤的 DP 题，实现的思路非常诡异，而且还卡空间卡时（这里补充一句：如果开 O2 还没过的大常数选手可以考虑手写 $\max,\min$ 函数以便卡常），需要运用滚动数组来进行空间优化

Luogu P2224 [HNOI2001]产品加工 题解