链接：https://ac.nowcoder.com/acm/problem/21873
来源：牛客网
题意：
牛牛的计算机一共有m块内存，现在有n条指令，每条指令是一个01序列
如果指令的第i个字符为1，说明这条指令需要访问第i块内存
每条指令的执行代价为k^2, k为新访问内存的数量，即之前的指令都没有访问到的内存数量
你可以随意安排n条指令的执行顺序，求执行完所有指令的最小代价
输入:
第一行先输入一个整数n，m(1 ≤ n ≤ 20)
接下来每行输入一个01字符串，长度不超过20
分析：
因为可以随意安排执行顺序，暴力就是20!，必然TLE，从记忆化搜索可以得到动态规划的做法
定义dp[i][j]，表示执行完前i次后状态为j的最小代价，状态j是什么呢？就是将前i次选的i条指令的编号压缩成一个数j，比如j的二进制为(110)，就代表前2次分别执行了编号为1和2的指令
定义val[i][j]表示到达dp[i][j]时，所选的指令所代表的字符串的状态，可以将每条指令看成一个二进制字符串，再将它压缩成十进制数表示状态，注意开滚动数组，否则要MLE
代码：
#include using namespace std;
const int inf = 0x3f3f3f3f;
int a[22],n,m,dp[2][1<<20],val[2][1<<20];
string s[22];
int cal(int x)//将二进制字符串压缩成十进制数
{
int res = 0,b = 1;
for(int i = 0;
i < m;
++i,b <<= 1) res += (s[x][i]=='1' ? b : 0);
return res;
}
int cal2(int a,int b)//计算a->b要花费的代价
{
int res = 0;
for(int i = 0;
i < 22;
++i){
if((a & (1<>n>>m;
memset(dp,inf,sizeof(dp));
for(int i = 0;
i < n;
++i) cin>>s[i];
for(int i = 0;
i < n;
++i){
a[i] = cal(i);
dp[0][1< 【动态规划----状压dp|牛客练习题---21873（牛牛的计算机内存【状压dp】）】上面的代码更具逻辑性，考虑当执行了一些指令后，下一次必然执行还未执行的一条指令，定义dp[j] 表示到达状态j时的最小花费，也就是执行了某些指令的最小花费，最后答案为dp[(1<
#include using namespace std;
const int inf = 0x3f3f3f3f;
int n,m,a[22],dp[1<<20],val[1<<20];
char s[22];
int cal(int x)//将二进制字符串压缩成十进制数
{
int res = 0,b = 1;
for(int i = 0;
i < m;
++i,b <<= 1) res += (s[i]=='1' ? b : 0);
return res;
}
int cal2(int a,int b)//计算a->b要花费的代价
{
int res = 0;
for(int i = 0;
i < 22;
++i){
if((a & (1<> n >> m;
for(int i = 0;
i < n;
++i) cin >>s,a[i] = cal(i);
memset(dp,inf,sizeof(dp));
dp[0] = 0;
for(int j = 0;
j < (1< tep){
dp[j|(1< 
