2011-0020

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

趁我还没忘记之前先把解题报告写了吧。

题目说有个工厂的老板很苛刻，希望工厂里的三台机器一直加工物品，没有一点时间空闲，然后还要三台机器同时结束工作，求最小的同时结束时间，不能满足就输出NO。

嗯，就我理解，这道题的实质是一个装箱问题？？给出n件物品在三个箱子中的价值，把这n件物品放进三个箱子里面，使得三个箱子里的东西价值恰好相等且最小？？然后就是一个状态空间的搜索？？状态空间是前i件物品装入之后三个箱子所有的可能情况，因为有三个箱子，所以至少是一个三维的空间，有同学想用二维的空间表示（当事人勿怪@@），形如dp[i][j]，其中i表示b箱中价值和a箱中的价值之差，j表示c箱中价值和a箱中价值之差，dp[i][j]中存放a的价值量。但是这样就会导致状态重叠（自创名词？？）如a=1,b=2,c=3和a=2,b=3,c=4在这样的状态空间表示方法中就会被记录在同一个状态点中，然后就会导致状态丢失wa了。

正确的方法有几种，其实就是几种常规的状态空间搜索方法。第一种可以把状态空间表示为dp[t][a][b][c]，存的是装入前t件物品，第一个箱子中的价值为a，第二个箱子中的价值为b，第三个箱子中的价值为c的状态是否存在。装入第t+1件物品后dp[t][a][b][c]的状态就转移到dp[t+1][a+va[i+1]][b][c]，dp[t+1][a][b+vb[i+1]][c]，dp[t+1][a][b][c+vc[i+1]]。其中va[i+1]，vb[i+1]，vc[i+1]分别是第i+1个物品装入a，b，c箱中的价值。需要更新的状态空间就是sum(a[i+1])*sum(b[i+1])*sum(c[i+1])。因为题目中所给出的条件，空间和时间复杂度都是O(40*120^3)。PS，如果每次都遍历120^3是很容易超时的，如果每次遍历前i项之和之积就会很快。

优化空间复杂度可以通过观察状态转移方程得出，每次的状态转移只和该状态的前一状态有关，所以可以用滚动数组实现，每次遍历上一次的状态空间，转移之后就得到了这次的状态空间。不过这种方法因为每次都要清空之前数组里的内容，结果反而比之后介绍的遍历当前状态空间的方法慢了。遍历当前的状态空间是利用了状态转移方程的单调性，只需要滚动数组一半的内存使用（省去了t，变成了dp[a][b][c]）。因为状态方程每次都转移都会递增，所以某个点的状态转移不会影响它下面的状态空间，所以逆推的话每个之后状态都是由它下面的三个状态决定的，所以如果我们自顶向下刷新整个状态空间不会使前后两个时间点（放入前i个和放入前i+1个）的状态空间重叠，但是如果自低向上更新则会有出现重叠，如果前一状态中dp[1][2][3]=true,dp[2][2][3]=false,a[i+1]=1，则在下一状态中dp[2][2][3]就为true,而此时dp[2][2][3]的状态还没有转移，就会wa。

另一种搜索方法就是在dp[a][b][c]的空间中用dfs搜索，用dfs的目的就是为了利用剪枝使得实际的搜索范围远远小于3^40。剪枝的方法主要是在a，b，c中任意一个大于当前最优解时停止搜索。不过如果输出NO的case则可能比较费时，所以运行时间会比直接遍历状态空间多很多。
不过鉴于在n比较小的情况下dfs会比遍历状态空间快不少，所以标程中把10以内的状态空间直接用dfs计算出来，然后再用第一种方法遍历状态空间得出最后的结果，因此只用了350ms（偷偷地说一句，dfs的加速真心不明显啊不明显）。

下面是我的代码：

{{{
#include<cstdio>
#include<utility>
#include<cstring>
using namespace std;

bool dp[128][128][128];
int main()
{
    int N;
    int a, b, c;
    int sa, sb, sc;
    while(EOF != scanf("%d", &N)){
        memset(dp, 0, sizeof dp);
        sa = sb = sc = 0;
        dp[0][0][0] = true;
        for(int i=0; i<N; i++){
            scanf("%d %d %d",&a, &b,&c);
            sa += a; sb += b; sc += c;
            for(int j=sa; j>=0; j--){
                for(int k=sb; k>=0; k--){
                    for(int l=sc; l>=0; l--){
                        dp[j][k][l] = (j>=a&&dp[j-a][k][l])||(k>=b&&dp[j][k-b][l])||(l>=c&&dp[j][k][l-c]);
                    }
                }
            }
        }
        int i;
        for(i=1; i<sa; i++){
            if(dp[i][i][i]){
                printf("%d\n", i);
                break;
            }
        }
        if(i == sa)
            printf("NO\n");
    }
    return 0;
}
}}}

by guinao 圡人不会调格式TAT

趁我还没忘记之前先把解题报告写了吧。

题目说有个工厂的老板很苛刻，希望工厂里的三台机器一直加工物品，没有一点时间空闲，然后还要三台机器同时结束工作，求最小的同时结束时间，不能满足就输出NO。

嗯，就我理解，这道题的实质是一个装箱问题？？给出n件物品在三个箱子中的价值，把这n件物品放进三个箱子里面，使得三个箱子里的东西价值恰好相等且最小？？然后就是一个状态空间的搜索？？状态空间是前i件物品装入之后三个箱子所有的可能情况，因为有三个箱子，所以至少是一个三维的空间，有同学想用二维的空间表示（当事人勿怪@@），形如dp[i][j]，其中i表示b箱中价值和a箱中的价值之差，j表示c箱中价值和a箱中价值之差，dp[i][j]中存放a的价值量。但是这样就会导致状态重叠（自创名词？？）如a=1,b=2,c=3和a=2,b=3,c=4在这样的状态空间表示方法中就会被记录在同一个状态点中，然后就会导致状态丢失wa了。

正确的方法有几种，其实就是几种常规的状态空间搜索方法。第一种可以把状态空间表示为dp[t][a][b][c]，存的是装入前t件物品，第一个箱子中的价值为a，第二个箱子中的价值为b，第三个箱子中的价值为c的状态是否存在。装入第t+1件物品后dp[t][a][b][c]的状态就转移到dp[t+1][a+va[i+1]][b][c]，dp[t+1][a][b+vb[i+1]][c]，dp[t+1][a][b][c+vc[i+1]]。其中va[i+1]，vb[i+1]，vc[i+1]分别是第i+1个物品装入a，b，c箱中的价值。需要更新的状态空间就是sum(a[i+1])*sum(b[i+1])*sum(c[i+1])。因为题目中所给出的条件，空间和时间复杂度都是O(40*120^{3)。PS，如果每次都遍历120}3是很容易超时的，如果每次遍历前i项之和之积就会很快。

优化空间复杂度可以通过观察状态转移方程得出，每次的状态转移只和该状态的前一状态有关，所以可以用滚动数组实现，每次遍历上一次的状态空间，转移之后就得到了这次的状态空间。不过这种方法因为每次都要清空之前数组里的内容，结果反而比之后介绍的遍历当前状态空间的方法慢了。遍历当前的状态空间是利用了状态转移方程的单调性，只需要滚动数组一半的内存使用（省去了t，变成了dp[a][b][c]）。因为状态方程每次都转移都会递增，所以某个点的状态转移不会影响它下面的状态空间，所以逆推的话每个之后状态都是由它下面的三个状态决定的，所以如果我们自顶向下刷新整个状态空间不会使前后两个时间点（放入前i个和放入前i+1个）的状态空间重叠，但是如果自低向上更新则会有出现重叠，如果前一状态中dp[1][2][3]=true,dp[2][2][3]=false,a[i+1]=1，则在下一状态中dp[2][2][3]就为true,而此时dp[2][2][3]的状态还没有转移，就会wa。

另一种搜索方法就是在dp[a][b][c]的空间中用dfs搜索，用dfs的目的就是为了利用剪枝使得实际的搜索范围远远小于3^40。剪枝的方法主要是在a，b，c中任意一个大于当前最优解时停止搜索。不过如果输出NO的case则可能比较费时，所以运行时间会比直接遍历状态空间多很多。

不过鉴于在n比较小的情况下dfs会比遍历状态空间快不少，所以标程中把10以内的状态空间直接用dfs计算出来，然后再用第一种方法遍历状态空间得出最后的结果，因此只用了350ms（偷偷地说一句，dfs的加速真心不明显啊不明显）。

下面是我的代码：

#include<cstdio>
#include<utility>
#include<cstring>
using namespace std;
bool dp[128][128][128];
int main()
{
    int N;
    int a, b, c;
    int sa, sb, sc;
    while(EOF != scanf("%d", &N)){
        memset(dp, 0, sizeof dp);
        sa = sb = sc = 0;
        dp[0][0][0] = true;
        for(int i=0; i<N; i++){
            scanf("%d %d %d",&a, &b,&c);
            sa += a; sb += b; sc += c;
            for(int j=sa; j>=0; j--){
                for(int k=sb; k>=0; k--){
                    for(int l=sc; l>=0; l--){
                        dp[j][k][l] = (j>=a&&dp[j-a][k][l])||(k>=b&&dp[j][k-b][l])||(l>=c&&dp[j][k][l-c]);
                    }
                }
            }
        }
        int i;
        for(i=1; i<sa; i++){
            if(dp[i][i][i]){
                printf("%d\n", i);
                break;
            }
        }
        if(i == sa)
            printf("NO\n");
    }
    return 0;
}

by guinao 圡人不会调格式TAT