【问题描述】
ib 被困在了一个美术馆里,她需要收集美术馆内的每种颜料才能获得逃出美
术馆的钥匙
美术馆由 n*m 的房间构成,每个房间里有一种颜料,解锁进入后就可以收集.
有的房间不能解锁,如果解锁的话会直接进入 Bad End.
ib 现在位于美术馆的最北面.她可以解锁东,南,西三面的房间,或者进入一个
已经解锁过的房间(包括起点)
ib 手上有一些玫瑰.解锁房间可能减少(或增加)ib 的玫瑰.我们定义每个房间
的权值为解锁会减少的 ib 的玫瑰数量(如果增加的话,为负值).
现在 ib 想知道,在收集所有颜料的情况下,最少减少的玫瑰数量(如果可以增加
的话,为负值).ib 还是个孩子,所以希望你告诉她.
【输入格式】
从文件 ib.in 中读入数据
第一行为三个正整数 n,m,k,k 代表颜料的数量.
接下来为 n 行 m 个整数,描述这个美术馆中颜料的分布情况
第 i 行第 j 个整数(a[i][j])代表从北数第 i 个,从西数第 j 个房间中的颜料,如果为
-1,代表此房间不能解锁
接下来为 n 行 m 个整数,描述这个美术馆房间的权值
第 i 行第 j 个整数(b[i][j])代表从北数第 i 个,从西数第 j 个房间的权值.
【输出格式】
输出到文件 ib.out 中.
为一行一个整数,代表最少减少的玫瑰数量(如果可以增加的话,为负值).
如果无解,输出”Bad End”(不含引号)
【样例输入 1】
4 4 3
1 1 1 1
1 -1 2 -1
1 3 -1 1
1 1 1 1
1 2 3 4
1 2 90 3
1 90 1 -1
-1 -1 -1 -1
【样例输出 1】
182
【样例说明 1】
下图是样例 1 的染料和权值分布情况示意图
Color 代表染料
Val 代表房间权值
房间上的小门代表这个房间会被解锁【样例输入 2】
4 4 2
2 2 2 -1
2 -1 2 -1
2 2 -1 1
2 2 2 2
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
【样例输出 2】
Bad End
【数据规模与约定】
对于 20%的数据,满足 n<=4,m<=4,k<=3
对于 60%的数据,满足 n*m<=50
对于 100%的数据,满足
1<=n*m<=200,1<=m<=n,1<=k<=5,a[i][j]=-1 或 1<=a[i][j]<=k,-1e9<=b[i][j]<=1e9
因为n×m<=200且m<=n，所以m最大为14，k最大为5
所以我们状态压缩
f[S][P]表示房间经过状态为S，颜料持有状态为P
枚举每一行转移
O(2^20*14)
转移分几步：
1.将上一行的已有状态S'，一个个减去1，转移到当前状态
显然这是可以的
2.枚举上一行所有状态S,一个个加上1，看是否可行，然后转移
为什么会有不可行？
10000001
00011000
显然是不行的，就是这一行的状态存在连续的一段不与上一行相交
3.对每一个这一行的房间状态捡到的颜料转移
f[S][P|val[S]]=min(f[S][P])
4.给每一个这一行的房间状态加上对应的权值
f[S][P]+=flower[S];
分别对应代码四种颜色
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long lol;
lol f[<<][<<],inf;
lol fl[<<],ans,b[][];
int a[][],val[<<];
int n,m,k;
int lowbit(int x)
{
return (x&(-x));
}
bool pd(int x,int y)
{
if (x>&&((x>>)&y)) return ;
if (x<(<<m)-&&((x<<)&y)) return ;
return ;
}
int main()
{int i,j,l;
freopen("ib.in","r",stdin);
freopen("ib.out","w",stdout);
cin>>n>>m>>k;
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
scanf("%lld",&b[i][j]);
}
}
memset(f,,sizeof(f));
inf=f[][];
f[(<<m)-][]=;
for (i=;i<=n;i++)
{
45 for (j=(1<<m)-1;j>=0;j--)
46 {
47 int x=j;
48 while (x)
49 {
50 for (l=0;l<(1<<k);l++)
51 f[j-lowbit(x)][l]=min(f[j-lowbit(x)][l],f[j][l]);
52 x-=lowbit(x);//除去最后一位1
53 }
54 }
55 for (j=0;j<(1<<m);j++)
56 {
57 int x=j;
58 while (x<(1<<m)-1)
59 {
60 int y=x;
61 x=x|(x+1);//给最靠左的0赋为1
62 if (pd(x^y,j))//判断这一状态与上一状态是否可达
63 {
64 for (l=0;l<(1<<k);l++)
65 f[j+(x^y)][l]=min(f[j+(x^y)][l],f[j][l]);
66 }
67 }
68 }
69 for (j=1;j<=m;j++)
70 {
71 if (a[i][j]==-1)
72 {
73 val[(1<<j-1)]=-1;
74 }
75 else val[(1<<j-1)]=1<<(a[i][j]-1);
76 fl[(1<<j-1)]=b[i][j];
77 }
78 for (j=1;j<(1<<m);j++)
79 {
80 if (val[j-lowbit(j)]==-1||val[lowbit(j)]==-1)
81 {
82 val[j]=-1;
83 for (l=0;l<(1<<k);l++)
84 f[j][l]=inf;
85 }
86 else
87 {
88 val[j]=val[lowbit(j)]|val[j-lowbit(j)];//合并出j状态所减少的玫瑰
89 fl[j]=fl[lowbit(j)]+fl[j-lowbit(j)];
90 for (l=0;l<(1<<k);l++)
91 f[j][l|val[j]]=min(f[j][l|val[j]],f[j][l]);//对于捡到的颜料转移
92 }
93 }
94 for (j=1;j<(1<<m);j++)
95 for (l=0;l<(1<<k);l++)
96 if (f[j][l]!=inf) f[j][l]+=fl[j];
97 }
ans=inf;
for (i=;i<(<<m);i++)
{
ans=min(ans,f[i][(<<k)-]);
}
if (ans>=inf)
cout<<"Bad End\n";
else cout<<ans;
}