題目描述
在電影《金陵十三釵》中有十二個(gè)秦淮河的女人要自我犧牲代替十二個(gè)女學(xué)生去赴日本人的死亡宴會(huì)。為了不讓日本人發(fā)現(xiàn)，自然需要一番喬裝打扮。但由于天生材質(zhì)的原因，每個(gè)人和每個(gè)人之間的相似度是不同的。由于我們這是編程題，因此情況就變成了金陵n釵。給出n個(gè)女人和n個(gè)學(xué)生的相似度矩陣，求她們之間的匹配所能獲得的最大相似度。
所謂相似度矩陣是一個(gè)n*n的二維數(shù)組like[i][j]。其中i,j分別為女人的編號(hào)和學(xué)生的編號(hào)，皆從0到n-1編號(hào)。like[i][j]是一個(gè)0到100的整數(shù)值，表示第i個(gè)女人和第j個(gè)學(xué)生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一樣。每個(gè)女人都需要找一個(gè)自己代替的女學(xué)生。
最終要使兩邊一一配對(duì)，形成一個(gè)匹配。請(qǐng)編程找到一種匹配方案，使各對(duì)女人和女學(xué)生之間的相似度之和最大。
輸入
第一行一個(gè)正整數(shù)n表示有n個(gè)秦淮河女人和n個(gè)女學(xué)生
接下來n行給出相似度，每行n個(gè)0到100的整數(shù)，依次對(duì)應(yīng)二維矩陣的n行n列。
輸出
僅一行，一個(gè)整數(shù)，表示可獲得的最大相似度。
樣例輸入
4
97 91 68 14
8 33 27 92
36 32 98 53
73 7 17 82
樣例輸出
354
思路：很容易想到的是類似于n皇后問題那樣，去挨個(gè)位置的去試，這樣的時(shí)間復(fù)雜度是O(n!)，n<=10的數(shù)據(jù)量是可以的，但是n>10的時(shí)候就不行了。n的數(shù)據(jù)量很少，因此我們可以采用狀壓的方法，將選擇的狀態(tài)利用二進(jìn)制串的方式表達(dá)出來。拿樣例來說，假如選擇了1,2,4列的話，表達(dá)為二進(jìn)制串就是11010.然后利用記憶化搜索，遇見重復(fù)的情況就可以直接返回了，大大減少了時(shí)間復(fù)雜度。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=15; const int maxm=(1<<14); int a[maxx][maxx]; int dp[maxx][maxm]; int n;inline int dfs(int x,int val) {if(dp[x][val]!=-1) return dp[x][val];int _max=0;if(x==n)//最后一行了，能用的位置肯定就只剩一個(gè)了，找到返回就ok了。{for(int i=1;i<=n;i++){int zz=(1<<(i-1));if(zz&val) return a[x][i];}}else{for(int i=1;i<=n;i++){int zz=(1<<(i-1));if(zz&val) _max=max(_max,a[x][i]+dfs(x+1,val-zz));//val-zz就代表著將那個(gè)位置由1變?yōu)?.}}return dp[x][val]=_max; } int main() {memset(dp,-1,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);int val=(1<<n)-1;printf("%d\n",dfs(1,val));return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]金陵十三钗（状压dp记忆化搜索）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。