1967. 秃了，也变强了 -- dp,dfs and similar

 1 

  #include 
 2 
 3 using namespace std;
 4 
 5 const int N = (1 << 8) + 1;
 6 
 7 int n, m;
 8 
 9 double a[N][N], dp[9][N][N];
10 
　　//二维数组的子矩阵和
11 double sum(int x, int y, int xx, int yy) { return a[x][y] - a[xx][y] - a[x][yy] + a[xx][yy]; }
12 
13 int main() {
14     ios::sync_with_stdio(false);
15     cin.tie(nullptr);
16     cin >> n;
17     m = (1 << n);
18     for (int i = 1; i <= m; i++) {
19         for (int j = 1; j <= m; j++) {
20             cin >> a[i][j];
21             a[i][j] += a[i - 1][j];
22             a[i][j] += a[i][j - 1];
23             a[i][j] -= a[i - 1][j - 1];//二维前缀和预处理
24         }
25     }
26     for (int l = n - 1; l >= 0; l--) {//倒着dp
27         int k = 1 << l, b = 1 << (n - l);
28         for (int i = m; i - k >= 0; i--) { //i-k,j-k与 0 比较防止越界
29             for (int j = m; j - k >= 0; j--) {
30                 double last = 0;
31                 for (int ii = min(i + k, m); ii >= i; ii--) {
32                     for (int jj = min(j + k, m); jj >= j; jj--) {
33                         last = max(last, dp[l + 1][ii][jj]);//数据量较小，暴力地更新max即可
34                     }
35                 }
　　　　　　　　　　　　// dp[l][i][j] = max([ min(i+k,m) >= ii >= 0 ][ min(j+k,m) >= jj >= 0] dp[l+1][ii][jj])] 
　　　　　　　　　　　　　　　　　　　　　　　　　　 + (sum[（i-k,j-k）,(i,j)] / log2(边长))
　　　　　　　　　　　　//为什么要除以b(1<36                 dp[l][i][j] = last + sum(i - k, j - k, i, j) / b;
37             }
38         }
39     }
40     double ans = 0;
41     for (int i = 1; i <= m; i++) {
42         for (int j = 1; j <= m; j++) {
43             ans = max(ans, dp[0][i][j]);//找到最大值
44         }
45     }
46     cout << fixed << setprecision(1);
47     cout << sum(0, 0, m, m) - ans << '\n';//结论就是 原始的总量 减去 掉发的最大值 
48     return 0;
49 }