CCYL Membership Activist

题解 P5911 【[POI2004]PRZ】

2021-02-20 20:20:52


(蒟蒻第一次写状压的题解,如内容有误欢迎大力指正)
翻了翻题解,发现貌似没有人写有关状压的前置知识,那我来介绍一下以让这篇题解不至于太短

个人理解,状压(状态压缩)的基本原理就是把一个整数(int 或 long long)当做数组来使用,让它来存储一种状态而不仅是一个数。具体的实现方法就是单独读取这个变量的某一二进制位。
其优势包括:

  1. 速度更快(只需使用位运算)
  2. 在存储有关该状态的信息时不需要用太复杂的数据结构
  3. 在欺负没学过状压的蒟蒻时看起来很帅

回归正题。
此题中 $n$ 的最大值为 16,也就意味着我们只需要一个 int 型整数就能存储所有人的状态(1 代表该人在桥上,0 代表不在),这时状压的优势就体现了出来。若用数组 $f$ 存储答案($f_i$ 代表在状态 $i$ 下通过所需的最短时间),则状态转换方程为$$f_i=min[f_i,f_j+time(f_i \otimes f_j)](i \supset j)$$ 好的,上代码。

数组及变量定义
wlmt 题目中的 $W$
n,w[i],t[i]同题目
cw[i] $i$ 状态下的总重
ct[i] $i$ 状态下用时
f 同方程中描述

//Luogu-P5911 Solution Version 题解版本 
//Luogu @W53729 (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<cstdio>
#include<cstring>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
#define maxcase_by_363523 (1<<16)-1
#define _363523_scan scanf
#define _363523_print printf
_Qijia AK IOI; //大佬保佑我AC(? 
int wlmt,n,w[20],t[20],cw[maxcase_by_363523+10],ct[maxcase_by_363523+10],f[maxcase_by_363523+10];
int max(int a,int b){
    return a>b?a:b; 
}
int min(int a,int b){
    return a<b?a:b; 
}
int main(){
    _363523_scan("%d%d",&wlmt,&n);
    const int cmaxcase_by_363523=(1<<n)-1;
    for(regint i=1;i<=n;++i) _363523_scan("%d%d",&t[i],&w[i]);
    for(regint i=0;i<=cmaxcase_by_363523;++i) //顺序循环所有状态 
        for(regint j=1;j<=n;++j)
            if(i&(1<<(j-1))/*判断第j个人是否在桥上*/) ct[i]=max(ct[i],t[j]),cw[i]+=w[j];//更新状态的时间和重量 
    memset(f,0x3f,sizeof(f)); //由于答案要求最小值 此处先设成最大 
    f[0]=0; //初始化 
    for(regint i=0;i<=cmaxcase_by_363523;++i){
        for(regint j=i;;j=i&(j-1)){ //顺序循环状态i的子集 
            if(cw[i^j]<=wlmt) f[i]=min(f[i],f[j]+ct[i^j]);
            if(!j) break; //终止循环 
        }
    }
    _363523_print("%d",f[cmaxcase_by_363523]);
    return 0;
}

感谢大佬阅读。