题意：要在一张网格纸上画出NOI图形，使得所占格子的权值和最大。
解：暴力DP即可...
从左往右，每个字母都可以被划分成三块，且每块都可用上下两维来表示。
于是一块一块的DP。考虑如何O(1)转移。显然只有N的中间那一块不好转移，别的都是直接转移。
N的三块的两个连接处之间，可以枚举必须持平的那个端点，另一个用前缀最值。
N第二块内部，考虑枚举后一个矩形的上边界，逐步扩展下边界。此时发现每扩展一步，可能的决策集合会增加：左边一格，下边界为刚扩展的那一格，上边界在枚举的上边界以上的所有状态。
于是对于每个下边界，预处理出上边界从上到下的一个前缀最值，加到决策集合里取max即可。
1 #include2 3 const int INF = 0x3f3f3f3f; 4 5 #define g f[FLAG] 6 #define h f[FLAG ^ 1] 7 8 int f[2][510][155][155], FLAG, n, m; 9 int s[155][510], p[510], temp[155][155]; 10 11 inline int getSum(int i, int l, int r) { 12 if(l > r) return 0; 13 return s[r][i] - s[l - 1][i]; 14 } 15 16 inline void out() { 17 for(int i = 1; i <= m; i++) { 18 for(int up = 1; up <= n; up++) { 19 for(int down = up; down <= n; down++) { 20 printf("%d ", g[i][up][down]); 21 } 22 } 23 puts(""); 24 } 25 puts(""); 26 return; 27 } 28 29 inline void outp() { 30 printf("p : "); 31 for(int i = 1; i <= m; i++) { 32 printf("%d ", p[i]); 33 } 34 puts(""); 35 puts(""); 36 return; 37 } 38 39 int main() { 40 //printf("%d \n", sizeof(f) / 1048576); 41 42 scanf("%d%d", &n, &m); 43 for(int i = 1; i <= n; i++) { 44 for(int j = 1; j <= m; j++) { 45 scanf("%d", &s[i][j]); 46 s[i][j] += s[i - 1][j]; 47 } 48 } 49 50 FLAG = 1; /// N 1 51 memset(g, ~0x3f, sizeof(g)); 52 for(int i = 1; i <= m; i++) { 53 for(int up = 1; up < n; up++) { 54 for(int down = up + 1; down <= n; down++) { 55 g[i][up][down] = std::max(0, g[i - 1][up][down]) + getSum(i, up, down); 56 } 57 } 58 } 59 60 //out(); 61 62 FLAG ^= 1; /// N 1.5 63 memset(g, ~0x3f, sizeof(g)); 64 for(int i = 1; i <= m; i++) { 65 for(int up = 1; up < n; up++) { 66 int large = -INF; 67 for(int down = n - 1; down >= up; down--) { 68 large = std::max(large, h[i - 1][up][down + 1]); 69 g[i][up][down] = large + getSum(i, up, down); 70 } 71 } 72 } 73 74 //out(); 75 76 FLAG ^= 1; /// N 2 77 //memset(g, ~0x3f, sizeof(g)); 78 memcpy(g, h, sizeof(h)); 79 for(int i = 1; i <= m; i++) { 80 memset(temp, ~0x3f, sizeof(temp)); 81 for(int down = 1; down <= n; down++) { 82 for(int up = 1; up <= down; up++) { 83 temp[down][up] = std::max(temp[down][up - 1], std::max(g[i - 1][up][down], h[i - 1][up][down])); 84 } 85 } 86 for(int up = 1; up <= n; up++) { 87 int large = temp[up - 1][up - 1]; 88 for(int down = up; down <= n; down++) { 89 large = std::max(large, temp[down][up]); 90 g[i][up][down] = std::max(large + getSum(i, up, down), h[i][up][down]); 91 } 92 } 93 } 94 95 //out(); 96 97 FLAG ^= 1; /// N 2.5 98 memset(g, ~0x3f, sizeof(g)); 99 for(int i = 1; i <= m; i++) {100 for(int down = 2; down <= n; down++) {101 int large = -INF;102 for(int up = down - 1; up >= 1; up--) {103 large = std::max(large, h[i - 1][up + 1][down]);104 g[i][up][down] = large + getSum(i, up, down);105 }106 }107 }108 109 //out();110 111 FLAG ^= 1; /// N 3112 memset(g, ~0x3f, sizeof(g));113 for(int i = 1; i <= m; i++) {114 for(int up = 1; up < n; up++) {115 for(int down = up + 1; down <= n; down++) {116 g[i][up][down] = std::max(h[i][up][down], g[i - 1][up][down] + getSum(i, up, down));117 }118 }119 }120 121 //out();122 123 /// get p : max of g124 memset(p, ~0x3f, sizeof(p));125 for(int i = 1; i <= m; i++) {126 p[i] = p[i - 1];127 for(int up = 1; up <= n; up++) {128 for(int down = 1; down <= n; down++) {129 p[i] = std::max(p[i], g[i][up][down]);130 }131 }132 }133 134 //outp();135 136 //out();137 138 //printf(" O 1 \n");139 140 FLAG ^= 1; /// O 1141 memset(g, ~0x3f, sizeof(g));142 for(int i = 5; i <= m; i++) {143 for(int up = 1; up < n - 1; up++) {144 for(int down = up + 2; down <= n; down++) {145 g[i][up][down] = p[i - 2] + getSum(i, up, down);146 }147 }148 }149 150 //out();151 152 //printf(" O 2 \n");153 154 FLAG ^= 1; /// O 2155 memset(g, ~0x3f, sizeof(g));156 for(int i = 1; i <= m; i++) {157 for(int up = 1; up < n - 1; up++) {158 for(int down = up + 2; down <= n; down++) {159 g[i][up][down] = std::max(h[i - 1][up][down], g[i - 1][up][down]) + getSum(i, up, up) + getSum(i, down, down);160 }161 }162 }163 164 //out();165 166 FLAG ^= 1; /// O 3167 memset(g, ~0x3f, sizeof(g));168 for(int i = 1; i <= m; i++) {169 for(int up = 1; up < n - 1; up++) {170 for(int down = up + 2; down <= n; down++) {171 g[i][up][down] = h[i - 1][up][down] + getSum(i, up, down);172 }173 }174 }175 176 //out();177 178 /// get p : max of g179 memset(p, ~0x3f, sizeof(p));180 for(int i = 1; i <= m; i++) {181 p[i] = p[i - 1];182 for(int up = 1; up < n - 1; up++) {183 for(int down = up + 2; down <= n; down++) {184 p[i] = std::max(p[i], g[i][up][down]);185 }186 }187 }188 189 //outp();190 191 //out();192 193 FLAG ^= 1; /// I 1194 memset(g, ~0x3f, sizeof(g));195 for(int i = 5; i <= m; i++) {196 for(int up = 1; up < n - 1; up++) {197 for(int down = up + 2; down <= n; down++) {198 g[i][up][down] = std::max(p[i - 2], g[i - 1][up][down]) + getSum(i, up, up) + getSum(i, down, down);199 }200 }201 }202 203 //out();204 205 FLAG ^= 1; /// I 2206 memset(g, ~0x3f, sizeof(g));207 for(int i = 1; i <= m; i++) {208 for(int up = 1; up < n - 1; up++) {209 for(int down = up + 2; down <= n; down++) {210 g[i][up][down] = std::max(g[i - 1][up][down], h[i - 1][up][down]) + getSum(i, up, down);211 }212 }213 }214 215 //out();216 int ans = -INF;217 218 FLAG ^= 1; /// I 3219 memset(g, ~0x3f, sizeof(g));220 for(int i = 1; i <= m; i++) {221 for(int up = 1; up < n - 1; up++) {222 for(int down = up + 2; down <= n; down++) {223 g[i][up][down] = std::max(g[i - 1][up][down], h[i - 1][up][down]) + getSum(i, up, up) + getSum(i, down, down);224 ans = std::max(g[i][up][down], ans);225 }226 }227 }228 229 //out();230 231 printf("%d\n", ans);232 return 0;233 }