(蒟蒻第一次写状压的题解,如内容有误欢迎大力指正)
翻了翻题解,发现貌似没有人写有关状压的前置知识,那我来水介绍一下以让这篇题解不至于太短
个人理解,状压(状态压缩)的基本原理就是把一个整数(int 或 long long)当做数组来使用,让它来存储一种状态而不仅是一个数。具体的实现方法就是单独读取这个变量的某一二进制位。
其优势包括:
- 速度更快(只需使用位运算)
- 在存储有关该状态的信息时不需要用太复杂的数据结构
在欺负没学过状压的蒟蒻时看起来很帅
回归正题。
此题中 $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;
}
感谢大佬阅读。