狀態壓縮動態規劃部分習題詳解
狀態壓縮動態規劃部分習題詳解
簡介
此處記錄了一些比較經典或巧妙的簡單狀壓dp題，粗略介紹了做題的一些思路。
經典子集類問題
原子彈
最近，火星研究人員發現了N個強大的原子。他們互相都不一樣。
這些原子具有一些性質。當這兩個原子碰撞時，其中一個原子會消失，產生大量的能量。
研究人員知道每兩個原子在碰撞時的能釋放的能量。
你要寫一個程式，讓它們碰撞之後產生最多的總能量。
輸入格式
有多組資料。
每組資料下的第一行是整數N（2 <= N <= 10），這意味著有N個原子：A1到AN。然後下面有N行，每行有N個整數。在第i行中的第j個整數表示當i和j碰撞之後產生的能量，並且碰撞之後j會消失。
所有整數都是正數，且不大於10000。輸入以n=0結尾。輸入資料不超過500個。
輸出格式
輸出N個原子碰撞之後產生的最大總能量。
輸入/輸出例子1
輸入：
2
0 4
1 0
3
0 20 1
12 0 1
1 10 0
0
輸出：
4
22
設
f
(
S
)
f(S)
f(S)表示原子集合為
S
S
S時釋放的最大能量，其中
1
1
1表示原子已消失，
0
0
0表示原子未使用。
顯然，
f
(
S
)
=
max
i
∈
S
,
j
∈
S
{
f
(
S
−
{
j
}
)
+
v
(
i
,
j
)
,
f
(
S
−
{
i
}
)
+
v
(
j
,
i
)
}
f(S) = \max_{i\in S,j\in S}\{f(S-\{j\})+v(i,j),f(S-\{i\})+v(j,i)\}
f(S)=i∈S,j∈Smax{f(S−{j})+v(i,j),f(S−{i})+v(j,i)}
其中，函數
v
(
i
,
j
)
v(i,j)
v(i,j)表示
i
i
i和
j
j
j碰撞且
j
j
j消失所產生的能量。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,map[15][15];
int f[2048],tot;
int main()
{
while(1)
{
scanf("%d",&n);
if(n == 0) break;
tot = (1<<n) - 1;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
scanf("%d",&map[i][j]);
for(int i = 0;i <= tot;i ++) f[i] = 0;
for(int k = 1;k <= tot;k ++)
for(int i = 0;i < n;i ++)
{
int s1 = 1<<i;
if((s1&k)>0)
for(int j = i + 1;j < n;j ++)
{
int s2 = 1<<j;
if((s2&k)>0)
{
int s3 = k - s1;
int s4 = k - s2;
f[k] = max(f[k],f[s3] + map[j+1][i+1]);
f[k] = max(f[k],f[s4] + map[i+1][j+1]);
}
}
}
printf("%d\n",f[tot]);
}
return 0;
}
最短路與狀壓DP結合
送禮物
給出一個n行m列的點陣，「.」 表示可通行格子，「#」 表示不可通行格子，
「K」 表示國王的初始位置，「Q」表示王后的位置，「G」表示該格子有一個禮物。
注意：國王、王后、禮物所在的格子可以認為是可通行格子的。
國王從開始位置出發，國王從當前格子可以走到上、下、左、右四個相鄰格子，當然前提是可通行格子。
國王從當前格子走到相鄰格子的時間是變化的，這取決於國王手頭上收集到的禮物的數量，
假如當前國王手頭上有y個禮物，那麼他從當前格子移動到相鄰格子的所用時間是y+1秒。
一旦國王進入某個有禮物的格子，他可以選擇取該格子的禮物，也可以選擇不取該格子的禮物。
取禮物這個動作可以認為是瞬間完成的，不需要時間。國王想收集到儘量多的禮物送給王后，
但是他到達王后所在的格子不能超過T秒，王后不想等太長時間。
注意：國王在收集禮物的途中可能多次走到相同的格子。
輸入格式
第一行：三個整數，n、m、T。 1 ≤ n, m ≤ 50。 1 ≤ T ≤10^9。
接下來是n行m列的點陣。‘G’的數量不超過16。 只有一個國王，一個王后。
輸出格式
一個整數，表示國王能送給皇后的禮物的最大數目
輸入/輸出例子1
輸入：
5 7 50
#....G#
###G###
#K...Q#
###.###
#G..GG#
輸出：
4
看到禮物數目範圍很小，考慮狀壓DP，顯然在動態規劃之前要處理出所有禮物兩兩之間的最小距離，注意到國王在收集禮物過程中可走到相同的格子，所以暴力給每一個禮物跑一遍單源最短路，手上就得到狀態轉移的方式。設
f
(
i
,
S
)
f(i,S)
f(i,S)表示現國王手上的禮物集合為
S
S
S，且最後一個拿到的禮物是
i
i
i，可知此時國王站在禮物
i
i
i處，顯然：
f
(
i
,
S
)
=
min
S
′
⊆
S
,
j
∈
S
′
{
f
(
j
,
S
′
)
+
d
i
s
(
j
,
i
)
×
c
n
t
(
S
)
}
f(i,S) = \min_{S'\sube S,j\in S'}\{f(j,S')+dis(j,i)\times cnt(S)\}
f(i,S)=S′⊆S,j∈S′min{f(j,S′)+dis(j,i)×cnt(S)}
其中，函數
d
i
s
(
x
,
y
)
dis(x,y)
dis(x,y)表示禮物
x
x
x和禮物
y
y
y之間的最小距離，函數
c
n
t
(
S
)
cnt(S)
cnt(S)表示
S
S
S中
1
1
1的個數。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const long long inf = 0xfffffffff;
typedef long long ll;
ll n,m,t,d[55][55],dis[55][55],f[66000][25];
int map[55][55],kx,ky,qx,qy,gx[55],gy[55],cnt,s1,ans,tot,num1;
int mark[55][55],nowx,nowy,nx,ny,dx[5] = {0,0,0,1,-1},dy[5] = {0,1,-1,0,0};
bool vis[55][55];
string s;
int cnt1(int x)
{
int tmp = 0;
for(int i = 1;i <= cnt;i ++)
if((x&(1<<(i-1))) > 0)
tmp ++;
return tmp;
}
void bfs(int sx,int sy)//跑最短路
{
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
d[i][j] = inf;
queue< pair<int , int > > q;
vis[sx][sy] = 1;
d[sx][sy] = 0;
q.push(make_pair(sx,sy));
while(!q.empty())
{
nowx = q.front().first;
nowy = q.front().second;
q.pop();
vis[nowx][nowy] = 0;
for(int i = 1;i <= 4;i ++)
{
nx = nowx + dx[i];ny = nowy + dy[i];
if(nx > 0 && nx <= n && ny > 0 && ny <= m )
if(d[nx][ny] > d[nowx][nowy] + 1 && map[nx][ny] == 1)
{
d[nx][ny] = d[nowx][nowy] + 1;
if(!vis[nx][ny])
{
vis[nx][ny] = 1;
q.push(make_pair(nx,ny));
}
}
}
}
for(int i = 0;i <= cnt + 1;i ++)
dis[mark[sx][sy]][i] = d[gx[i]][gy[i]];
return ;
}
int main()
{
memset(mark,128,sizeof(mark));
//read data
scanf("%lld%lld%lld",&n,&m,&t);
for(int i = 1;i <= n;i ++)
{
cin >> s;
for(int j = 0;j < s.size();j ++)
{
switch(s[j])
{
case '.':
map[i][j+1] = 1;
break;
case '#':
map[i][j+1] = 0;
break;
case 'G':
cnt ++;
gx[cnt] = i;gy[cnt] = j + 1;
mark[i][j+1] = cnt;
map[i][j+1] = 1;
break;
case 'K':
kx = i;ky = j + 1;
map[i][j+1] = 1;
break;
case 'Q':
qx = i;qy = j + 1;
map[i][j+1] = 1;
break;
}
}
}
mark[kx][ky] = 0;mark[qx][qy] = cnt + 1;
gx[0] = kx;gy[0] = ky;
gx[cnt + 1] = qx;gy[cnt + 1] = qy;
for(int i = 0;i <= cnt+1;i ++)
for(int j = 0;j <= cnt + 1;j ++)
dis[i][j] = inf;
for(int i = 0;i <= cnt + 1;i ++)//求出兩兩之間的最短路程
bfs(gx[i],gy[i]);
tot = 1<<(cnt+1) - 1;
for(int i = 0;i <= tot;i ++)
for(int j = 0;j <= cnt+1; j ++)
f[i][j] = inf;
for(int i = 1;i <= cnt;i ++)//初始化
f[(1<<(i-1))][i] = dis[0][i];
for(int s = 0;s <= tot; s ++)//狀壓DP
{
num1 = cnt1(s);
for(int i = 1;i <= cnt;i ++)
if((s&(1<<(i-1))) > 0)
{
s1 = s - (1<<(i-1));
for(int j = 1;j <= cnt;j ++)
if((s1&(1<<(j-1))) > 0)
f[s][i] = min(f[s][i],f[s1][j]+dis[j][i]*num1);
}
}
for(int s = 0;s <= tot;s ++)//最後再判斷一次，看能否在T內到皇后的地方
{
num1 = cnt1(s);
for(int i = 1;i <= cnt;i ++)
if((s&(1<<(i-1))) > 0)
{
ll sum = f[s][i] + dis[i][cnt+1]*(num1+1);
if(sum <= t)
ans = max(ans,num1);
}
}
printf("%d",ans);
return 0;
}
P3959寶藏
P3959 寶藏
看到寶藏屋的數目很少，又想到狀壓dp。
考慮到開拓一間新寶藏屋的費用與開拓道路起點有關，並且與最開始免費打通的寶藏屋有關，設
f
(
i
,
j
,
S
)
f(i,j,S)
f(i,j,S)表示開發的寶藏屋集合為
S
S
S，本次開發到
j
j
j，最開始打通的寶藏屋為
i
i
i。
發現有：
f
(
i
,
j
,
S
)
=
min
k
∈
S
,
k
≠
j
{
f
(
i
,
k
,
S
−
{
j
}
)
+
min
e
:
k
→
j
{
d
i
s
(
e
)
}
×
g
(
i
,
k
)
}
f(i,j,S) = \min_{k\in S,k\ne j}\{f(i,k,S-\{j\})+\min_{e:k\rightarrow j}\{dis(e)\}\times g(i,k)\}
f(i,j,S)=k∈S,k=jmin{f(i,k,S−{j})+e:k→jmin{dis(e)}×g(i,k)}
其中，函數
d
i
s
(
e
)
dis(e)
dis(e)表示道路
e
e
e的長度，函數
g
(
i
,
j
)
g(i,j)
g(i,j)表示從
i
i
i到
j
j
j所經過的寶藏屋的數目。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
using namespace std;
const long long inf = 0xfffffffff;
typedef long long ll;
ll f[20][5000],g[20][5000][20],ans = inf,num;
int n,m,x,y,z,u,v,s1,tot,map[6000],tmp;
int head[50],cnt;
struct edge{
int next;
int to;
ll val;
}e[10005];
void myinit()
{
for(int i = 0;i < 20;i ++)
for(int j = 0;j < 5000;j ++)
f[i][j] = inf;
for(int i = 0;i < 20;i ++)
for(int j = 0;j < 5000;j ++)
for(int k = 0;k < 20;k ++)
g[i][j][k] = inf;
}
void addedge(int from,int to,int v)
{
cnt ++;
e[cnt].next = head[from];
e[cnt].to =to;
e[cnt].val = v;
head[from] = cnt;
cnt ++;
e[cnt].next = head[to];
e[cnt].to = from;
e[cnt].val = v;
head[to] = cnt;
return ;
}
int main()
{
myinit();
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
map[(1<<(i-1))] = i;
for(int i = 1;i <= m;i ++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
}
tot = (1<<n)-1;
for(int i = 1;i <= n;i ++)//初始化
{
f[i][(1<<(i-1))] = 0;
g[i][(1<<(i-1))][i] = 1;//一邊dp一邊更新g(i,j)
}
for(int k = 1;k <= n;k ++)
for(int s = 0;s <= tot;s ++)
for(tmp = s;tmp;tmp = (tmp&(tmp-1)) )
{
u = map[(tmp&(-tmp))];
for(int i = head[u];i != 0;i = e[i].next)//列舉出邊
{
v = e[i].to;
if((s&(1<<(v-1))) > 0)
{
s1 = s - (1<<(v-1));
num = g[k][s1][u];
if(f[k][s] > f[k][s1] + e[i].val*num)
{
f[k][s] = f[k][s1] + e[i].val*num;
for(int j = 1;j <= n;j ++) g[k][s][j] = g[k][s1][j];//更新g(i,j)
g[k][s][v] = num + 1;//更新g(i,j)
}
}
}
}
for(int i = 1;i <= n;i ++)
ans = min(ans,f[i][tot]);
printf("%lld",ans);
return 0;
}
旅遊
有n (n <= 50)個小島,編號從0到n-1。一開始你在小島0。島與島之間只能用船來擺渡。有f(1 <= f <= 10)個公司提供船票。
每個公司提供的船票有不同的路線，第i個公司有k_i條單向路線，一條路線就是允許你從一個小島a到另一個小島b，一張票只能挑一條路線。
這f個公司在n個小島都設有售票點，但同一個公司的票在不同的小島可能價格不一樣，而在同一個小島，你買了某個公司j的票,那麼你挑j公司任意一條單向線路的費用都是相同的。
現在的任務是：從小島0到其它各個小島的最小費用是多少？
不過還有個麻煩的條件：任意時刻你手上的票不能超過3張，而且同一個公司不能有兩張票，也就是說你到了任意一個小島j,手頭上只可能剩0張票或1張票或2張票，而且這些票都是從不同公司買的。
一開始你在小島0，沒有票，出發前最多能買3張票。
如果某個小島不能到達，那麼輸出-1。
提示：最小費用路徑可能經過同一個城市多次，見樣例 2.
輸入格式
多組測試資料。
第一行：一個整數r, 表示有r組測試資料。1 <= r <= 3。
每組測試資料格式如下：
第一行：n和f。1 <= n <= 40,1 <= f <= 10。
接下來有f行，第i行描述第i個公司的線路資訊，第一整數是k_i(1 <= k_i <= 20)，
然後有k_i條單向線路，每條線路就是兩個整數a和b，表示公司i有從小島a到小島b的路線。
接下來有n行，每行有f個整數，第i行的第j個整數表示在第i個小島購買第j個公司的一張票的費用，
費用是不超過1000的正整數。
0 <= i < n。1 <= j <= f。
輸出格式
共r行，每行n-1個數，表示從小島0到小島1的最小費用，小島0到小島2的最小費用…小島0到小島n-1的最小費用。
輸入/輸出例子1
輸入：
2
5 2
3 0 1 1 2 2 3
2 0 1 2 3
1 10
20 25
50 50
1000 1000
1000 1000
4 4
1 1 0
1 0 1
1 0 2
1 2 3
1 1 1000 1000
1000 1000 10 100
1000 1000 1000 1000
1000 1000 1000 1000
輸出：
1 11 31 -1
1 12 112
樣例解釋
第一組測試資料解釋：
有2個售票公司，5個小島。第1個公司提供3條單向路線，分別是0到1, 1到2, 2到3。第2個公司提供2條單向路線，分別是0到1，2到3。我們稱第一個公司是公司A，第二個公司是公司B。我們在小島0買一張A公司的票費用是1元，買一張B公司的票費用是10元。在小島1買一張A公司的票費用是20元，買一張B公司的票費用是25元。在小島2買一張A公司的票費用是50元，買一張B個公司的票費用是50元。在小島3買一張A公司的票費用是1000元，買一張B公司的票費用是1000元。在小島4買一張A公司的票費用是1000元，買一張B公司的票費用是1000元。那麼從小島0到小島1最小費用是：在小島0買一張A公司0到1的單向票，費用是1。從小島0到小島2最小費用是：在小島0買一張B公司的0到1的單向票，費用是10，同時還在小島0買一張A公司的從1到2的單向票，費用是1，那麼用11元就可以從小島0到達小島2了。 從小島0到小島3的最小費用是：在小島0買一張A公司的0到1的單向票，費用是1，同時在小島0買一張B公司的2到3的票，費用是10，那麼用Ａ公司的票就可以到達小島１，然後再從小島１買一張Ａ公司的1到２的單向票費用是20，到了小島2後在用手頭上那張未用的票到達小島3，總費用是31。小島4無法到達。
第二組測試資料解釋：
設四個公司為A ,B，C，D。
從小島0到達小島3的最小費用是: 在小島0買一張A公司的票和一張B公司的票，用B公司的票到達小島1，在小島1買一張C公司的票和一張D公司的票，用A公司的票回到小島0，現在手頭上還有兩張票：公司C的票和公司D的票，然後用公司C的票到達小島2，用公司D的票到達小島3。
仔細閱讀，注意其中幾個細節：在任意小島上都能買任意公司的票；任何時刻手上的票不能超過3張；可多次走同一路線，即可多次去同一個小島。第一個細節，我們發現對於一種持票情況，某些票可能是來到這個島之前就買好的，有些票是在這個島上買的，處理的時候可以分類討論。第二個細節告訴我們可以預處理出
1
1
1的數量不超過3的所有狀態，或者加判斷。第三個細節給我們帶來不少麻煩，為了保證能夠及時更新，我們想到最短路中的更新方法，將佇列遷移到dp上來，就能夠及時更新狀態。設
f
(
i
,
S
)
f(i,S)
f(i,S)表示在第
i
i
i個島上，手裡持票情況為
S
S
S，可以得到：
f
(
i
,
S
)
=
min
{
min
k
∈
S
1
,
c
o
n
k
(
j
,
i
)
=
1
{
f
(
j
,
S
1
)
}
,
min
k
∈
S
{
f
(
i
,
S
−
k
)
+
p
(
k
,
i
)
}
}
f(i,S) = \min\{\min_{k\in S_1,con_k(j,i)=1}\{f(j,S_1) \},\min_{k\in S}\{f(i,S-{k})+p(k,i)\}\}
f(i,S)=min{k∈S1,conk(j,i)=1min{f(j,S1)},k∈Smin{f(i,S−k)+p(k,i)}}
其中，函數
c
o
n
k
(
x
,
y
)
con_k(x,y)
conk(x,y)表示公司
k
k
k的路線中，是否有一條從
x
x
x到
y
y
y，函數
p
(
k
,
i
)
p(k,i)
p(k,i)表示公司
k
k
k的票在
i
i
i島上的價格。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int inf = 2139062143;
int n,cp,k,r,u,v,cnt,f[45][1050],tot,tmp,s1,num;
int map[15][45][45],p[15][45],d[50];
bool vis[50];
int cnt1(int x)
{
int tmp = 0;
for(int i = 1;i <= cp;i ++)
if((x&(1<<(i-1))) > 0)
tmp ++;
return tmp;
}
void solve()
{
//init
memset(d,127,sizeof(d));
memset(f,127,sizeof(f));
memset(map,0,sizeof(map));
memset(p,0,sizeof(p));
//read
scanf("%d%d",&n,&cp);
for(int i = 1;i <= cp;i ++)
{
scanf("%d",&k);
for(int j = 1;j <= k;j ++)
{
scanf("%d%d",&u,&v);
map[i][u][v] = 1;
}
}
for(int i = 0;i < n;i ++)
for(int j = 1;j <= cp;j ++)
scanf("%d",&p[j][i]);
//dp
tot = 1<<(cp+1) - 1;
for(int i = 0;i <= tot;i ++)//在第一個島上買票
{
num = cnt1(i);
if(num > 3) continue;
tmp = 0 ;
for(int j = 1;j <= cp;j ++)
if((i&(1<<(j-1))) > 0)
tmp += p[j][0];
f[0][i] = tmp;
}
memset(vis,0,sizeof(vis));
queue<int > q;
q.push(0);
while(!q.empty())
{
int i = q.front();
q.pop();
vis[i] = 0;
for(int s = 0;s <= tot;s ++)//enumrate the status of tickets
{
num = cnt1(s);
if(num > 3) continue;
for(int j = 1;j <= cp;j ++)//We buy tickets on this island
if((s&(1<<(j-1))) > 0)
{
s1 = s - (1<<(j-1));
f[i][s] = min(f[i][s],f[i][s1]+p[j][i]);
}
for(int j = 1;j <= cp;j ++)//We have bought tickets on other island
if((s&(1<<(j-1))) > 0)
{
s1 = s - (1<<(j-1));
for(int k = 0;k < n;k ++)
if(map[j][i][k])//Use this ticket to travel from i to k
{
d[k] = min(d[k],f[i][s]);//update the minimum distance
if(f[k][s1] > f[i][s])//update the next status
{
f[k][s1] = f[i][s];
if(!vis[k])
{
vis[k] = 1;
q.push(k);//keep updating
}
}
}
}
}
}
for(int i = 1;i < n;i ++)
{
if(d[i] == inf) printf("-1 ");
else printf("%d ",d[i]);
}
printf("\n");
}
int main()
{
scanf("%d",&r);
for(int i = 1;i <= r;i ++)
solve();
return 0;
}
經典網格類
鋪地磚
輸入格式
輸入包含多個測試用例。
每個測試用例是由兩個整數數位:高度h和大型矩形的寬度w。
輸入由h = w = 0時終止。否則 1 < = h,w < = 11。
輸出格式
每個測試資料輸出一個答案。
輸入/輸出例子1
輸入：
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
輸出：
1
0
1
2
3
5
144
51205
考慮用輪廓線，注意橫磚一次佔兩個位，並且注意最後一行不能有突出，詳解在參考程式碼中，注意細節。
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
using namespace std;
int h,w,tot;
long long f[25][25][30000];
bool vis[25][25][30000];
long long dfs(int x,int y,int s)
{
if(x > h) return 1;//this rectangle is full of bricks
if(y > w) return dfs(x+1,1,s);//next row
if(vis[x][y][s]) return f[x][y][s];
vis[x][y][s] = 1;
int s1 = 1<<(y-1);
if((s1&s)>0) //the current grid is occupied by a vertical brick
{
f[x][y][s] = dfs(x,y+1,s-s1);// As for the next row,it won't be affected by this vertical brick
return f[x][y][s];
}
long long tmp1 = 0;
if(x < h)//place a vertical brick on this grid
tmp1 = dfs(x,y+1,s1+s);//the placement of this brick will influence the way of placing bricks on the next row
int s2 = 1<<y;long long tmp2 = 0;
if(y < w)//place a transverse brick on this grid
if((s2&s)==0)//to check whether we can place this transverse brick or not
tmp2 = dfs(x,y+1,s+s2);
f[x][y][s] = tmp1 + tmp2;
return f[x][y][s];
}
int main()
{
while(1)
{
cin>>h>>w;
if(h == 0 && w == 0) break;
tot = (1<<(w+1))-1;
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
cout << dfs(1,1,0) << endl;
}
return 0;
}
一筆畫
由於小毛同學智商不高，理解不了真正的一筆畫問題，於是他就開始研究一種變形的一筆畫問題。
給出 n 行 m 列的點陣，每個點是一個字元： 「．」 或 「#」 ，其中「#」表示該點是障礙物。
現在小毛的問題是： 他最少要畫多少筆才能把點陣裡所有的「．」都覆蓋完畢（被小毛畫到的點就會被覆蓋）。
小毛的筆有點奇怪：小毛每次只能在某一行或某一列畫，小毛當然想一筆就把某一行或某一列畫完，
但很遺憾，在任何時候都不允許小毛畫的那一段點陣含有障礙物。
還有一點更奇怪： 已經被畫過的點，不能重複被畫。
輸入格式
第一行： n , m 表示點陣行數和列數 。 0 < n, m <=10
接下來有n行， 每行有m個字元，「．」 或 「#」
輸出格式
一個整數， 小毛最少要畫多少筆。
輸入/輸出例子1
輸入：
2 4
.##.
....
輸出：
3
輸入/輸出例子2
輸入：
3 4
....
....
....
輸出：
3
看似毫無頭緒的搜尋，但看到n，m的範圍很小，先想想狀壓dp。
想到#等價於在此格畫過，整張圖可轉化為畫過和沒畫過兩種狀態，然而這樣規定狀態導致我們處理的時候無法分清什麼時候橫著畫過，什麼時候豎著畫過，所以轉換思路。
我們將豎著畫過的格子標記為
1
1
1，橫著畫過的格子標記為
0
0
0，遇到不可畫格子特判，將每一行的狀態轉化為
01
01
01串，再仔細想想，情況豁然開朗：
- 對於豎著畫過的格子，我們要判斷上一行同一列的格子是否也豎著畫，如果是，這一格就不需要再畫一筆
- 對於橫著畫的格子，一個完整連續段算作畫一筆
- 對於不可畫格子，不算作一筆，且一筆橫畫至此斷開
用行列式直接dp即可
f
(
i
,
S
)
=
min
S
′
{
f
(
i
−
1
,
S
′
)
+
g
(
S
,
S
′
)
}
f(i,S)=\min_{S'}\{f(i-1,S')+g(S,S')\}
f(i,S)=S′min{f(i−1,S′)+g(S,S′)}
其中，函數
g
g
g表示增加的一筆畫次數
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
const int inf = 2139062143;
int n,m,f[15][1050],tmp,tmp1,ans = inf,tot,b[15];
//1 refers to drawing vertically and 0 refers to drawing transversely
//regard # as 0
bool map[15][15],flag;
string s;
bool check(int now,int x)//the position of # in the map can't be 1 in the status
{
if((b[now]&x) > 0) return 0;
else return 1;
}
int main()
{
memset(f,127,sizeof(f));
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
{
cin >> s;
for(int j = 0;j < s.size();j ++)
if(s[j] == '#')
{
map[i][j+1] = 1;
b[i] += (1<<j);//record the status
}
}
tot = 1<<(m+1) - 1;
for(int s = 0;s <= tot; s++)//initalization
{
if(!check(1,s)) continue;
flag = 0;tmp = 0;
for(int j = 1;j <= m;j ++)
{
if((s&(1<<(j-1))) > 0)//draw vertically
{
tmp ++;
flag = 0;
}
else
{
if(map[1][j])
{
flag = 0;
continue;
}//draw transeversely
if(flag) continue;//draw with one stroke
else
{
flag = 1;
tmp ++;
}
}
}
f[1][s] = tmp;
if(1 == n) ans = min(ans,f[1][s]);
}
for(int i = 2;i <= n;i ++)
{
for(int s = 0;s <= tot;s ++)//the status of last row
{
if(!check(i-1,s)) continue;
for(int s1 = 0;s1 <= tot;s1 ++)//the status of this row
{
if(!check(i,s1)) continue;
flag = 0;tmp = 0;tmp1 = 0;
for(int j = 1;j <= m;j ++)
{
if((s1&(1<<(j-1))) > 0)
{
flag = 0;
//draw transeversely on the last row
if((s&(1<<(j-1))) == 0) tmp1 ++;//draw vertically this row
}
else
{
if(map[i][j])
{
flag = 0;
continue;
}
if(flag) continue;
else flag = 1,tmp ++;
}
}
f[i][s1] = min(f[i][s1],f[i-1][s] + tmp1 + tmp);
// cout << i << ' ' << s1 << ' ' << f[i][s1] << endl;
if(i == n) ans = min(ans,f[i][s1]);
}
}
}
if(ans == inf) printf("0");
else printf("%d",ans);
return 0;
}
其他型別
單詞
輸入格式
輸出格式
輸入/輸出例子1
輸入：
3
a
ab
abc
輸出：
4
輸入/輸出例子2
輸入：
3
a
ab
c
輸出：
4
輸入/輸出例子3
輸入：
4
baab
abab
aabb
bbaa
輸出：
5
當所有字串變換成使得它們的公共字首最長時，trie樹的結點樹最少
看到資料範圍
1
≤
n
≤
16
1\le n\le 16
1≤n≤16，自然先想到狀壓DP
由於字串可以任意變換，只需統計字串中每一種字母出現的個數就可以方便表示字串，且方便接下來的操作
設
S
S
S表示被選取加入trie樹的字串的集合，
S
′
⊆
S
S'\subseteq S
S′⊆S，
f
(
S
)
f(S)
f(S)表示在狀態
S
S
S下trie樹的最少結點數，
p
(
S
)
p(S)
p(S)表示在
S
S
S狀態下，最大公共字首的長度
則有：
f
(
S
)
=
f
(
S
′
)
+
f
(
S
−
S
′
)
−
p
(
S
)
f(S) = f(S')+f(S-S')-p(S)
f(S)=f(S′)+f(S−S′)−p(S)
其中，函數
p
(
S
)
p(S)
p(S)表示在字串集合為
S
S
S的情況下的最大公共字首的長度
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<fstream>
using namespace std;
const int inf = 0xfffffff;
int n,f[65540],tmp,tot,cnt[65540][30];
string s[25];
int main()
{
// freopen("test.txt","r",stdin);
cin >> n;
tot = (1<<n)-1;
for(int i = 0; i <= tot;i ++) f[i] = inf;
for(int i = 0;i <= tot;i ++)
for(int j = 0;j < 26;j ++)
cnt[i][j] = inf ;
for(int i = 1;i <= n;i ++)
{
cin >> s[i];
tmp = 1<<(i-1);
f[tmp] = s[i].size();
for(int j = 0;j < 26;j ++) cnt[tmp][j] = 0;
for(int j = 0;j < s[i].size();j ++) cnt[tmp][s[i][j]-'a'] ++;//統計字母
}
f[0] = 0;
for(int i = 1;i <= tot;i ++)
{
tmp = 0;
for(int j = 1;j <= n;j ++)
if(((1<<(j-1))&i) > 0)
for(int k = 0;k < 26;k ++)
cnt[i][k] = min(cnt[i][k],cnt[(1<<(j-1))][k]);求公共字首長度
for(int k = 0;k < 26;k ++)
tmp += cnt[i][k];
for(int j = i&(i-1);j;j = (j-1)&i)
{
int k = i - j;
f[i] = min(f[i],f[k]+f[j]-tmp);
}
}
cout << f[tot]+1 << endl;//最後還有空結點
return 0;
}
隊伍統計
n<=20，又是狀壓DP
設
f
(
i
,
S
)
f(i,S)
f(i,S)表集合
S
S
S中的人已經排好隊，排列合法且隊尾是
i
i
i，則有：
f
(
i
,
S
)
=
∑
S
′
⊆
S
,
j
∈
S
c
n
t
(
S
′
)
<
k
f
(
j
,
S
′
)
f(i,S)=\sum_{S'\sube S,j\in S}^{cnt(S')<k}f(j,S')
f(i,S)=S′⊆S,j∈S∑cnt(S′)<kf(j,S′)
其中，函數
c
n
t
(
S
)
cnt(S)
cnt(S)表示
S
S
S中的矛盾關係個數
#include<iostream>
#include<cstdio>
using namespace std;
const int modnum = 1000000007;
int n,m,k,tot,s1;
int u[505],v[505],tmp;
bool map[30][30];
long long f[35][1048580],ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
tot = (1 << n) - 1;
for(int i = 1;i <= m;i ++)
{
scanf("%d%d",&u[i],&v[i]);
map[u[i]][v[i]] = 1;
}
f[0][0] = 1;
for(int s = 1; s <= tot; s ++)//enumerate all the states
for(int i = 1;i <= n;i ++)//enumerate the last number in this sequence
{
tmp = 0;
if(((1<<(i-1))&s) > 0)
{
s1 = s - (1<<(i-1));
for(int j = 1;j <= n;j ++)
if(((1<<(j-1))&s1) > 0)
{
if(map[i][j]) tmp ++;//if the last number is i , it will cause tmp arguements
if(tmp > k) break;
}
if(tmp > k) continue;
for(int j = 0;j <= (k-tmp);j ++)//enumerate last status
f[tmp+j][s] = (f[tmp+j][s]%modnum + f[j][s1]%modnum)%modnum;
}
}
for(int i = 0;i <= k;i ++)//sum up the answer
ans = (ans%modnum + f[i][tot]%modnum)%modnum;
printf("%lld",(ans%modnum));
return 0;
}