P2224 [HNOI2001] 产品加工——奇怪的状态优化

· · 个人记录

初见想法

记dp_{i,tA,tB}为循环到第 i 个物品，A的时间为 tA ,B的时间为 tB 时,能否填满

空间复杂度O(n^3)，显然连开都开不出来

初见之后的乱搞

空间开不出来，于是决定拿记搜+set乱水，但是写到一半发现记忆化加了没意义，因为事实上没有办法统计每个物品对答案的贡献

28pts的dfs：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=6e3+5;

struct item{
    int t1,t2,t3;
}a[MAXN];

int n;

int dfs(int t1,int t2,int it){
    if(it>n) return max(t1,t2);
    int res=2e9;
    if(a[it].t1) res=min(res,dfs(t1+a[it].t1,t2,it+1));
    if(a[it].t2) res=min(res,dfs(t1,t2+a[it].t2,it+1));
    if(a[it].t3) res=min(res,dfs(t1+a[it].t3,t2+a[it].t3,it+1));
    return res;
}//

void work(){
    scanf("%d",&n);

    for(int i=1;i<=n;++i)
        scanf("%d%d%d",&a[i].t1,&a[i].t2,&a[i].t3);

    printf("%d",dfs(0,0,1));
}//

int main(){
    work();
    return 0;
}

正解

既然空间不足，考虑优化状态

容易想到的是把第 i 维用滚动数组压掉

但是剩下的仍然有 9 \times 10^8 级别，依然开不下

而且时间复杂度依旧有 O(n^3) 无法接受

那么接下来就是我看不懂但是大受震撼的优化了：

将状态由dp_{tA,tB}表示 tA,tB 的可能性转化为dp_{tA} 时 tB 的最小值

也就是说将影响答案的两个因素之一的状态转变为维护的值了，于是在时间和空间上都压低了一维

那么原来维护的可行性也就不需要维护了，因为在这种情况下几乎必然可以通过调整各个 tA 时的 tB 使得能够生产 n 个物品

另：状态转移方程和滚动优化的一些细节：

code：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN=6e3+5;

struct item{
    int t1,t2,t3;
}a[MAXN];

int n;

int dp[MAXN*5],ans=inf;

void work(){
    scanf("%d",&n);

    for(int i=1;i<=n;++i)
        scanf("%d%d%d",&a[i].t1,&a[i].t2,&a[i].t3);

    memset(dp,0,sizeof(dp));
//  dp[0]=0;

    for(int i=1;i<=n;++i){
        for(int j=n*5;j>=0;--j){
            int res1=inf,res2=inf,res3=inf;
            if(a[i].t1 && j>=a[i].t1) res1=dp[j-a[i].t1];
            if(a[i].t2) res2=dp[j]+a[i].t2;
            if(a[i].t3 && j>=a[i].t3) res3=dp[j-a[i].t3]+a[i].t3;
            dp[j]=min(res1,min(res2,res3));
        }
    }

    for(int i=0;i<=n*5;++i) ans=min(max(i,dp[i]),ans);

    printf("%d",ans);
}//

int main(){
    work();
    return 0;
}

试图总结这种优化使用的时机

多个参数影响最终答案，难以在过程中比较
维护的东西有可以优化掉的可能性