【题解】P7098 [yLOI2020] 凉凉

· · 题解

前言

预处理巨多的状压好题

思路

我不会爆搜啊，太麻烦了。

直接将 \text{DP} 怎么做。

首先需要很多的预处理：

1、处理在每一个深度 j 建立某一个铁路线 i 花费的价格 \text{cost}_{i,j}。

2、处理出铁路线 i 和铁路线 j 能否在同一个深度建立线路 vis_{i,j}。

3、处理出在深度为 i 的时候，在这一层深度修建的铁路线的状态为 S 价钱 g_{i,S}。

处理完这些就可以进行非常短的 \text{DP} 过程了。

限制我们计算价钱的量为深度 \text{dep} ，以及状态 S, 那么就考虑设置两维 \text{DP}。

设置 f_{i,S} 已经弄完了前 i 深度的铁路线，现在建立完的铁路线编号的状态为 S 的最短价格。

既然我们预处理完了，那么很显然的状态转移就是：

f_{i,S}=\min_{s\in S} \{ f_{i-1,S\oplus s}+g_{i,s}\}

我们可以用枚举子集的方法避免暴力枚举状态判断。

奇怪的复杂度大约为 ：O(n^2+2^{14}n^2+2^{14}+2^{14}n)。(枚举子集的时间复杂度不会算/kk)

可以非常完美的通过此题。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int N=15;
const int M=1e5+9;
const int K=(1<<15);
const long long int INF=1e18+9;//要开大一点/cg 
int dep[N][M];//深度为 i 的地铁经过了地铁站 j ，的花费
int cnt[N];//表示第 i 条地铁经过的站点个数 
int sub[N][M];//第 i 条地铁经过的站点编号。
int n,m;
long long int f[N][K];//明显跟深度有关，所以就设前i深度，修建的铁路线状态为j的最小花费
long long int g[N][K];//在深度为i时，该层修建状态为j的花费 
long long int cost[N][N];//第i条铁路在深度为j修建时的花费 
bool vis[N][N];//询问第i条铁路和第j条铁路能否修建在一个道路上 
int stk[N],top;
int read()
{
    int f=1,x=0;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^'0');s=getchar();}
    return f*x;
} 
void Prepare()
{
    for(int i=1;i<=n;i++)
        sort(sub[i]+1,sub[i]+1+cnt[i]);//排序，便于查找 
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            vis[i][j]=vis[j][i]=true;
            int x=1,y=1;//一种省时间的方法，序号排好之后，我们可以不断比较编号大小，慢慢递增寻找相同点
            while(x<=cnt[i] and y<=cnt[j])
            {
                if(sub[i][x]==sub[j][y])
                {
                    vis[i][j]=vis[j][i]=false;  
                    break;//不能在同一条线路上 
                }   
                if(sub[i][x]<sub[j][y]) x++;
                else if(sub[i][x]>sub[j][y]) y++;
            }
        }
    }
    for(int s=1;s<(1<<n);s++)//枚举所有状态 
    {
        top=0;
        for(int i=1;i<=n;i++)
            if(s&(1<<(i-1)))//有戏
            {
                stk[++top]=i;
                for(int j=1;j<top;j++)
                    if(!vis[i][stk[j]])//看来没戏了/kk
                    {
                        for(int k=1;k<=n;k++)//把所有都变为极大值
                            g[k][s]=INF;
                    }
                if(f[1][s]==INF)//没救了，赋为极大值
                    break;
                for(int j=1;j<=n;j++)
                    g[j][s]+=cost[i][j];
                //深度为j时修建状态为s的铁路，加上第i条铁路在j深度修建时的总价钱。 
            }
    }
    for(int s=1;s<(1<<n);s++)
        f[1][s]=g[1][s];//初始化第一行 
    return;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            dep[i][j]=read();
    for(int i=1;i<=n;i++)
    {
        cnt[i]=read();//输入个数
        for(int j=1;j<=cnt[i];j++)
            sub[i][j]=read();
        for(int j=1;j<=n;j++)
            for(int k=1;k<=cnt[i];k++)
                cost[i][j]+=dep[j][sub[i][k]];
    }
    Prepare();
    for(int i=2;i<=n;i++)
    {
        for(int S=0;S<(1<<n);S++)
        {
            f[i][S]=f[i-1][S];//初始化,加入这个不选 
            for(int s=S;s;s=(s-1)&S)
                f[i][S]=min(f[i][S],f[i-1][S^s]+g[i][s]);
        }   
    } 
    cout<<f[n][(1<<n)-1]<<endl;
    return 0;
}