本人剛學壓縮dp，只能對這些水題寫題解 一方面對自己的理解有加深作用 另一方面希望和各位大牛交流交流。。。。。

如果有對狀態dp不太了解的童鞋可以參考入門知識：http://wenku.baidu.com/link?url=AnHFiSXoqPvVCxObtwNYEUCVfPL6_2QeuA9B1zkdmVk59Fy_f-CwZCuHwtHl6Wc9zbMmIyaaOOpSR1sRVvTGff3d-4D4SfhD2k-Gf-ijrOG

以及我最開始看的狀態dp水題：http://poj.org/problem?id=3254

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int dp[16][1<<17];///表示最大相親的好感和 6 void solve(int n,int a[16][16]) 7 { 8 int w=1<<n; 9 memset(dp,0,sizeof(dp));///清0，用0表示沒有此狀態 10 for(int i=0; i<n; i++) 11 { 12 dp[0][1<<i]=a[0][i];///對于出狀態進行預處理，即第一行的狀態暴力一下 13 } 14 for(int i=0; i<n-1; i++)///第一層循環遍歷0~n-1行 15 { 16 for(int j=0; j<w; j++)///第二層循環遍歷0~（1<<n）的狀態 17 { 18 if(dp[i][j]!=0)///對于非0的狀態進行處理 19 for(int k=0; k<n; k++) 20 { 21 if(!(j&(1<<k)))///j里有1<<k的狀態 22 { 23 if(dp[i+1][j+(1<<k)]<=dp[i][j]+a[i+1][k])///求第i+1行的最大值 24 dp[i+1][j+(1<<k)]=dp[i][j]+a[i+1][k]; 25 } 26 } 27 } 28 } 29 int ans=0; 30 for(int i=0; i<w; i++) 31 { 32 if(ans<dp[n-1][i]) 33 ans=dp[n-1][i];///對于最后一行的狀態遍歷求dp 34 } 35 printf("%d\n",ans); 36 } 37 int main() 38 { 39 int a[16][16]; 40 int t; 41 scanf("%d",&t); 42 while(t--) 43 { 44 int n; 45 scanf("%d",&n); 46 for(int i=0; i<n; i++) 47 for(int j=0; j<n; j++) 48 { 49 scanf("%d",&a[i][j]); 50 } 51 solve(n,a); 52 } 53 }

?

轉載于:https://www.cnblogs.com/guyahan/p/5436580.html

總結

以上是生活随笔為你收集整理的hrbust1841再就业（状态压缩dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。