vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 P1777 【帮助】

posted on 2021-01-15 17:41:03 | under 题解 |

毒瘤题目。

(CYjian巨佬竟然说简单?他是神仙不要在意)

首先,我们要取肯定是把连续相同的一段都取出来,因此我们可以用一个二元数组 $(b_{i},w_{i})$ 代替 $a$,其中 $b_{i}$ 为 $a$ 中第 $i$ 段连续且相同的数的大小, $w_{i}$ 为其段长。

接下来考虑 dp。第一想法是令 $f_{i,j}$ 表示前 $i$ 段取出 $j$ 本书,但对于类似于 $25,26,25$ 的情况,取出 $26$ 后它旁边的两个 $25$ 就又凑成了一段,因此后面的那个 $25$ 并不会产生贡献。所以我们的 dp 还需要记录前 $i$ 段取出 $j$ 本书后留在书架上的最后一本书的高度是多少。也就是令 $f_{i,j,l}$ 表示前 $i$ 段取出 $j$ 本书,留在书架上且最靠后的一本书的高度为 $l$ 时的最小混乱度。

但事情并没有那么简单,因为我们只是取出了 $j$ 本书,我们还没有考虑把这些书按某个顺序放回书架的问题。显然,如果选出了一本高度为 $h_{i}$ 的书,我们肯定要把它放到高度和它相同的书的旁边。如果书架上没有高度与之相同的书呢?那答案就会 $+1$。因此,我们还要记录书架上还剩哪些高度的书,由于高度介于 $25$ 和 $32$ 之间,因此我们可以把高度离散化,然后状压。

令 $f_{i,j,t,l}$ 表示前 $i$ 段取 $j$ 本,留在书架上的书的高度的集合为 $t$,书架上的最后一本书的高度为 $l$ 的最小混乱度。转移方程为 $f_{i,j,t,l}=f_{i-1,j-w_{i},t,l}$(将第 $i$ 段的 $w_{i}$ 本书取出),以及 $f_{i,j,t,b_{i}}=\min_{p|(1<<b_{i})=t;l=0\sim mx}(f_{i-1,j,p,l}+[b_{i}\not=l])$(不取第 $i$ 段),其中 $<<$ 为左移位操作, $mx$ 为离散化后的 $a$ 数组的最大值 $+1$(因为还要用一个数代表没有最后一本书也就是前面的书全部被取走的情况)。最后 $dp_{m,j,t,l}$ 对应的答案就是 $dp_{m,j,t,l}+calc(S\oplus t)$,其中 $m$ 为 $a$ 数组的段数, $S$ 为最开始书架上的书的高度的集合对应的二进制数, $calc(x)$ 表示二进制数 $x$ 所含 $1$ 的个数。

每组测试数据的时空复杂度为 $O(m\times k\times mx\times 2^{mx})$。因此不需要啥滚动数组(不过最后一个点有点卡常,我是吸氧才过的)。

代码如下(点个赞再走吧QAQ,谢谢您!):

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=1<<8;
int dp[101][101][N][9],a[N],b[N],w[N],top,n,k,rp; 

int cal(int x){
    int cnt=0;
    fo(i,0,7) if(x&(1<<i)) ++cnt;
    return cnt;
}

void solve(){
    int AC[10]={0};
    top=0;
    fo(i,1,n) a[i]=read()-25,AC[a[i]]++;
    fo(i,0,9) if(AC[i]) AC[i]=top++;
    fo(i,1,n) a[i]=AC[a[i]];
    int p=1<<top,mx=top;
    top=0;
    int last=1;
    a[0]=a[1];
    fo(i,1,n) if(a[i]!=a[i-1]){
        b[++top]=a[i-1];
        w[top]=i-last;
        last=i;
    }
    b[++top]=a[n];
    w[top]=n+1-last;
    //fo(i,1,top) printf("%d ",b[i]);puts("");
    //fo(i,1,top) printf("%d ",w[i]);puts("");
    //memset(dp,0x3f,sizeof dp);
    fo(i,1,top) fo(j,0,k) fo(t,0,p-1) fo(l,0,mx) dp[i][j][t][l]=3000; 
    dp[1][0][1<<b[1]][b[1]]=1;
    dp[1][w[1]][0][mx]=0;
    fo(i,2,top){
        fo(j,w[i],k){
            fo(t,0,p-1){
                //花w[i]的代价取出i这一段
                fo(l,0,mx){
                    dp[i][j][t][l]=dp[i-1][j-w[i]][t][l];
                } 
            }
            fo(t,0,p-1){
                //不取出这一段
                fo(l,0,mx){
                    dp[i][j][t|(1<<b[i])][b[i]]=min(dp[i][j][t|(1<<b[i])][b[i]],dp[i-1][j][t][l]+(b[i]!=l?1:0));
                }  
            }           
        }
        //不取出这一段 
        fo(j,0,w[i]-1)
            fo(t,0,p-1)
                fo(l,0,mx){
                    dp[i][j][t|(1<<b[i])][b[i]]=min(dp[i][j][t|(1<<b[i])][b[i]],dp[i-1][j][t][l]+(b[i]!=l));
                }
        //fo(j,0,k) fo(t,0,p-1) fo(l,0,mx) printf("(%d,%d,%d,%d)=%d\n",i,j,t,l,dp[i][j][t][l]);
    }
    int ans=2000;
    fo(i,0,k)
        fo(j,0,p-1)
            fo(qaq,0,mx) ans=min(ans,dp[top][i][j][qaq]+cal((p-1)^j));
    printf("Case %d: %d\n\n",rp,ans);
}

int main(){
    while(1){
        n=read(),k=read();
        if(n==0&&k==0) break;
        rp++;
        solve();
    }   
    return 0;
}
/*
-------------------------------------------------
*/