HDU 1565 方格取数(1) （状态压缩DP）

ACM

题目地址：
HDU 1565 方格取数(1)

题意：
中文。

分析：
dp[i][j]表示前i行状态j的最优解。
先预处理出符合条件的数,17000+个(n在20以内)。
不过感觉复杂度挺高的会T，但是却能A。
这题的正解应该是最小割，回头补下。

代码：

/*
*  Author:      illuz 
  
   
*  File:        1565_dp.cpp
*  Create Date: 2014-09-19 23:30:19
*  Descripton:  dp
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 1<<21; int n, st[N], stn; int dp[2][N]; int ans, g[25][25]; void pre() { repf (i, 0, (1<<20)) { if (i & (i<<1)) continue; else st[stn++] = i; } } void solve() { if (n == 0) { cout << 0 << endl; return; } int tot = 1<
       
        > n) { repf (i, 0, n - 1) repf (j, 0, n - 1) cin >> g[i][j]; solve(); } return 0; }