P2530

· · 题解

题面

给三种物品，共有 n 个，先拿前 10 个，然后把任意一种物品全装箱，然后往后拿再补到 10 个，剩余的补不到就取完。

求装箱最少次数。

题解

DP。

根据题意，设 f_{i,x,y,z} 为前 i 个，x 个 A，y 个 B，z 个 C 的最少装箱次数。

然后直接根据题面，当 x+y+z=10 时，进行一次装箱，然后再拿物品，那么可以由此转移状态。

可以想到，给一个物品装箱后，手中多出的空间就是装箱前手中这个物品的数量，然后就可以往后拿物品。

所以就有：

然后我们要推式子中的 nxtA,nxtB,nxtC。

装箱后往后取的物品中，可能三种物品都有。而此时手中刚装箱的物品数量被清空，其他物品都是原来的数量。

因此，取完物品后，刚装箱物品的数量就是新取物品的区间中这个物品的数量，而其它物品的数量就是原来的数量加上新取物品的区间中这个物品的数量。

所以可以预处理一个前缀和数组，记录前缀物品 A，B，C 的数量，然后就可以在 O(1) 复杂度内算出 nxtA,nxtB,nxtC。

最终答案就是 f_{n,0,0,0}。

由于 DP 没有后效性，所以此题中，以所有状态为点，所有转移为边权为 1 的有向边来构图，可以构成一个有向无环图，且每个点出度都为 3。

然后此时就是要求从 \{10,cntA,cntB,cntC\} 到达 \{n,0,0,0\} 的最短路。

由于是 DAG，所以直接 BFS 一遍就可以找到答案。

注意特判 n \le 10 的情况。

但其实代码中可以不用建图，这里提到建图只是方便理解用 BFS 枚举的原因。

详情请见代码，可加深理解。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
char ch[102];
int f[102][12][12][12]; //f[i][x][y][z]表示前i个，手中x个A，y个B，z个C的最优答案 
int cnt[102][3];
bool vis[102][12][12][12];
struct node {
    int k,x,y,z;
};
int nxt(int l,int r,int z) {return cnt[r][z]-cnt[l][z];}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        cin>>ch[i];
        cnt[i][ch[i]-'A']++;
        for(int j=0;j<3;j++) cnt[i][j]+=cnt[i-1][j]; //cnt 储存前缀的 A,B,C 数量 
    }
    if(n<=10) {
        printf("%d",(cnt[n][0]>0)+(cnt[n][1]>0)+(cnt[n][2]>0));
        return 0;
    }
    //n 不超过 10 时直接输出答案 
    memset(f,0x3f,sizeof f);
    f[10][cnt[10][0]][cnt[10][1]][cnt[10][2]]=0;
    queue<node> q;
    q.push({10,cnt[10][0],cnt[10][1],cnt[10][2]});
    while(1) {
        int k=q.front().k,x=q.front().x,y=q.front().y,z=q.front().z;
        if(k==n) break;
        //由于使用 bfs 枚举，所有状态组成的图被分成了一层又一层，而当 k=n 时图是最后一层，可以直接统计答案 
        q.pop();
        if(vis[k][x][y][z]) continue;
        vis[k][x][y][z]=1; 
        //判重优化 
        int nt=min(k+x,n);
        f[nt][nxt(k,nt,0)][y+nxt(k,nt,1)][z+nxt(k,nt,2)]=min(f[nt][nxt(k,nt,0)][y+nxt(k,nt,1)][z+nxt(k,nt,2)],f[k][x][y][z]+1);
        q.push({nt,nxt(k,nt,0),y+nxt(k,nt,1),z+nxt(k,nt,2)});
        //给 A 装箱，再拿物品，转移状态 
        nt=min(k+y,n);
        f[nt][x+nxt(k,nt,0)][nxt(k,nt,1)][z+nxt(k,nt,2)]=min(f[nt][x+nxt(k,nt,0)][nxt(k,nt,1)][z+nxt(k,nt,2)],f[k][x][y][z]+1);
        q.push({nt,x+nxt(k,nt,0),nxt(k,nt,1),z+nxt(k,nt,2)});
        //给 B 装箱，再拿物品，转移状态  
        nt=min(k+z,n);
        f[nt][x+nxt(k,nt,0)][y+nxt(k,nt,1)][nxt(k,nt,2)]=min(f[nt][x+nxt(k,nt,0)][y+nxt(k,nt,1)][nxt(k,nt,2)],f[k][x][y][z]+1);
        q.push({nt,x+nxt(k,nt,0),y+nxt(k,nt,1),nxt(k,nt,2)});
        //给 C 装箱，再拿物品，转移状态 
    }
    while(!q.empty()) {
        int x=q.front().x,y=q.front().y,z=q.front().z;
        f[n][0][0][0]=min(f[n][0][0][0],f[n][x][y][z]+(x>0)+(y>0)+(z>0));
        q.pop();
        //将 k=n 的答案汇集到 {n,0,0,0} 的状态 
    }
    printf("%d",f[n][0][0][0]);
    return 0;
}