ZOJ Problem Arrangement 递推+状压 - c++编程基础

对于dp[ i ][ j ] , 设 i 的二进制中 1 的个数为 Si。

则dp[ i ][ j ]表示在前Si行中，选取 i 的二进制对应的列所能得到分数 j 的方案数。

则递推方程为:

dp[ t ][ k ] += dp[ i ][ j ] ， Si +1 == St && （t 的二进制与 i 的二进制有且只有一位不一样，换言之，只能在Sl行选取未在前 Si 行选取的一个列）。

最后 dp[1<<(n-1)][m]即为可行方案总数，而总的方案数为 n！。

又因此为01分布，所以期望为 dp[1<<(n-1)][m]/(n!)，求出最大公约数化简即可。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) const double PI = acos(-1.0); using namespace std; int p[14][14]; struct N { LL ans,row; }dp[4100][510]; LL gcd(LL a,LL b) { if(b == 0) return a; return gcd(b,a%b); } LL mul[14]; int main() { int T; int n,m,i,j,k,Max; for(mul[0] = 1,i = 1; i <= 12; ++i) { mul[i] = mul[i-1]*i; } scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { scanf("%d",&p[i][j]); } } Max = (1<
           
            = m) { dp[1<<(i-1)][m].ans++; dp[1<<(i-1)][m].row = 1; } else { dp[1<<(i-1)][p[1][i]].ans++; dp[1<<(i-1)][p[1][i]].row = 1; } } LL r; for(i = 1; i < Max; ++i) { for(j = 0; j <= m; ++j) { if(dp[i][j].ans) { r = dp[i][j].row+1; for(k = 1; k <= n; ++k) { if((i&(1<<(k-1))) == 0) { if(j+p[r][k] >= m) { dp[i+(1<<(k-1))][m].ans += dp[i][j].ans; dp[i+(1<<(k-1))][m].row = r; } else { dp[i+(1<<(k-1))][j+p[r][k]].ans += dp[i][j].ans; dp[i+(1<<(k-1))][j+p[r][k]].row = r; } } } } } } if(dp[Max][m].ans) { LL temp = gcd(mul[n],dp[Max][m].ans); printf("%lld/%lld\n",mul[n]/temp,dp[Max][m].ans/temp); } else { printf("No solution\n"); } } return 0; }