学步园

昨天的月赛题。DP题。不会做，搜了之后凑合理解明白了。

学了下位运算的状态压缩 = =。。。很强大的东西。。。

详见解说http://blog.csdn.net/magicnumber/archive/2011/02/13/6182891.aspx

#include <cstdio><br /> #include <cstdlib><br /> #include <iostream><br /> #include <string.h><br /> #include <queue><br /> #include <limits.h><br /> using namespace std;<br /> int map[12][12];<br /> int dp[2000];<br /> int bin[13] = {0,1,2,4,8,16,32,64,128,256,512,1024};<br /> int main()<br /> {<br /> int i,k,p,maxx,n;<br /> while( ~scanf("%d",&n) && n )<br /> {<br /> memset(dp,0,sizeof(dp));<br /> for(i=1; i<=n; i++)<br /> for(k=1; k<=n; k++)<br /> scanf("%d",&map[i][k]);</p> <p> for(i=0; i<bin[n+1]; i++)<br /> for(k=1; k<=n; k++)<br /> if( (i & bin[k]) == 0 )<br /> for(p=1; p<=n; p++)<br /> if( (i & bin[p]) == 0 && p != k )<br /> dp[i+bin[p]] = max(dp[i]+map[k][p],dp[i+bin[p]]);<br /> maxx = 0;<br /> for(i=0; i<bin[n+1]; i++)<br /> if( dp[i] > maxx )<br /> maxx = dp[i];<br /> printf("%d/n",maxx);<br /> }<br /> return 0;<br /> }<br />