P1777 帮助题解

lenlen · 2022-11-23 19:38:12 · 题解

一道不错的状压 DP 题，有 UVA 账号的话甚至可以再去水一个黑题（可惜我没有 UVA 账号 QWQ，~~赶紧注册~~）。

Problem

题目大意：定义一个序列的混乱度为该序列的连续段的段数，你可以从一个长度为 n 的序列中取 k 个数出来，再插入到原序列里面去，问最小的混乱度是多少。

数据范围： n,k \leq 100,25 \leq a_i \leq 32。

Solution

看到 25 \leq a_i \leq 32，又发现只是要考虑数字相同的连续段段数，所以跟数字大小没有关系，只要保证原序列中相同的数一直相同即可，最简单的方法就是所有 a_i 减去 25，当然也可以离散化。

然后我们可以发现一点，如果你把 k 取出来了，而序列中还有 k，那么显然混乱度是不会增加的，你只需要吧取出来的 k 都放在序列中 k 的左右就好了。

我分可以定义状态： dp_{i,j,k} 表示前 i 个数取了 j 个且未取的（即序列中还有的数的种类，使用状态压缩）状态为 k 的最小混乱度，但是很明显可以发现，若我们不取，而它正好和前面一个不取的数相同，混乱度也是不会改变的，所以我们还需要记一维 s 表示前面一个没取的数为 s。

因为该题目枚举状态中再由前面的状态转移比较困难（当然不排除大佬这么做，反正我只是个蒟蒻），我们枚举已知状态来推出后面的状态会容易很多。

定义 dp_{i,j,k,s} 表示前 i 个数选了 j 个数出去，且序列中（指 [1,i] 未被选择出去的数）的状态为 k，且前一个未被选出去的数为 s 的最小混乱度，初始赋值 dp_{1,0,2^{a_1},a_1}=1,dp_{1,1,0,8}=0，其它全为 inf，转移方程：

dp_{i+1,j,k \mid 2^{a_{i+1}},a_{i+1}}=\min(dp_{i,j,k,s}+[s \not= a_{i+1}])

dp_{i+1,j+1,k,a_{i+1}}=\min(dp_{i,j,k,s})

说明一下： dp_{1,0,2^{a_1},a_1} 表示第一个不选，dp_{1,1,0,8}=0 表示选出第一个，但我们可以发现，现在序列中是没有数的，所以下一个不选出来的数必然会增加 1 的混乱度，所以我们要保证初始的 dp_{1,1,0,s} 要保证 s 和所有数都不相等，而 s 的范围是 25-25 \leq s \leq 32-25 \Rightarrow s \in [0,7]，所以我们初始要不在这个范围内。上述转移中 [A] 表示若 A 为真就返回 1，否则返回 0，即若数不同，那么混乱值要加 1。

然后我们可以发现空间复杂度是 O(m 2^{m-1} n^2)，其中 m=32-25+1=8，可以发现是不会超的，不需要滚动数组。算法优秀的话也是不需要卡常的，所以这题时空其实都不需要可以卡，挺合理的。

Code

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=102,inf=1e9+7;
int dp[N][N][1<<8|2][9],gt[1<<8],ans=inf;
int n,k,a[N],sum,tot;
int mx(int x,int y){return x>y?x:y;}
int mi(int x,int y){return x<y?x:y;}
void init()
{
    ans=inf;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=k;j++)
    for(int k=0;k<(1<<8);k++)
    for(int s=0;s<=8;s++) dp[i][j][k][s]=inf;
}
int main()
{
    for(int i=0;i<(1<<8);i++)
    {
        for(int j=7;j>=0;j--)
        if((i>>j)&1) gt[i]++;//提前预处理出每种状态的选出来的个数
    }
    while(1)
    {
        scanf("%d%d",&n,&k);sum=0;//总状态
        if(!n&&!k) break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=25,sum|=(1<<a[i]);
        init();//初始化
        dp[1][0][1<<a[1]][a[1]]=1;
        dp[1][1][0][8]=0;
        for(int i=1;i<n;i++)
        for(int j=0;j<=k;j++)
        for(int k=0;k<(1<<8);k++)
        for(int s=0;s<=8;s++) 
        {
            if(dp[i][j][k][s]==inf) continue;
            dp[i+1][j][k|(1<<a[i+1])][a[i+1]]=mi(dp[i+1][j][k|(1<<a[i+1])][a[i+1]],dp[i][j][k][s]+(a[i+1]==s?0:1));
            dp[i+1][j+1][k][s]=mi(dp[i+1][j+1][k][s],dp[i][j][k][s]);
        }
        for(int i=0;i<=k;i++)
        for(int j=0;j<(1<<8);j++)
        for(int k=0;k<=7;k++) 
        {
            if(dp[n][i][j][k]==inf) continue;
            ans=mi(ans,dp[n][i][j][k]+gt[sum^j]);//sum为总种类，j为当前情况下序列中未被抽出的数的种类，那么sum^j就是全部抽出来的数的种类，这些数不管放哪里混乱度都会+1
        }
        printf("Case %d: %d\n\n",++tot,ans);
    }
    return 0;
}

最后感谢 @EnofTaiPeople 的线下讲解。

P1777 帮助 题解

Problem

Solution

Code

P1777 帮助题解