这种类型的题目似乎很常见——方格棋盘，搜索某种状态。你也许会大喊：“嘿，伙计，为什么不再来一份？……”
但是我就他喵的又敲了2个钟头，其中莫名其妙的错误就和绵羊身上的毛一样多。
在这之前我要承认这是一道很繁琐的题目。第一题目没有给出棋盘的长宽，需要处理字符串；第二当你敲下第200行代码之后再简单的题也会突然变得复杂起来。
单纯的搜索是不可能的。N*N= 225，这样的数据规模已经注定了纯搜的失败。接着考虑分行。
上一行的情况直接决定了下一行。这就够了。当然，不是像某些题目一样，第一行决定之后，你就可以泡一杯咖啡，坐着等待AC了。但是当第一行决定之后，第二行的情况始终是有限种并且可记录。为什么不在开始时预处理下这些变换呢？这样就节省下无数时间。
考虑到每一格只有两种情况：取或者不取。N<15，第一选择就是位操作。
现在设状态为F（i，j），表示第i行下取到j时的最大值。每一种状态都是唯一确定且满足最优子结构。故DP得最终解。
#include <iostream>#include <string>using namespace std;#define setMax(x,y) ( x = x > y ? x : y )int N, a[16][16], b[16][40000];int c[16][40000];int p[16];string str;int ans = 0;typedef struct
...{
int u, v;
} Num;Num trans[50000];int len;int checkOne ( int n )...{ int i; for ( i = 0; i < 14; i ++ )
...{ if ( n & p[i] && n & p[i + 1] ) return 0;
} return 1;}void init ()...{ str += ' '; string sub; int i, j = 0; while ( str.size () ) ...{ i = str.find_first_of ( ' ' ); sub = str.substr ( 0, i ); int sum = 0; str = str.substr ( i + 1, str.size () ); for ( i = 0; i < sub.size (); i ++ ) sum = sum * 10 + sub[i] - '0'; a[N][j ++] = sum; } N ++;}int checkPebbles ( int r, int n )...{ int i, sum; for ( i = 0, sum = 0; i < N; i ++ ) ...{ if ( n & p[i] ) sum += a[r][i]; } return sum;}void dp ()...{ int i, j; memset ( b, 0xff, sizeof ( b ) ); for ( i = 0; i < N; i ++ ) ...{ for ( j = 0; j < ( 1 << N ); j ++ ) ...{ c[i][j] = checkPebbles ( i, j ); } } ans = 0; int u, v; for ( j = 0; j < len; j ++ ) ...{ u = trans[j].u, v = trans[j].v; if ( u == 0 && v < ( 1 << N ) ) ...{ //printf ( "%d %d ", u, v ); b[0][trans[j].v] = c[0][trans[j].v]; setMax ( ans, b[0][trans[j].v] ); } } //printf ( "%d ", ans ); for ( i = 1; i < N; i ++ ) ...{ for ( j = 0; j < len; j ++ ) ...{ u = trans[j].u, v = trans[j].v; if ( u >= ( 1 << N ) || v >= ( 1 << N ) ) continue; if ( b[i - 1][u] == -1 ) continue; //printf ( "%d %d %d %d %d %d ", i, u, v, b[i][v], b[i - 1][u], c[i][v] ); setMax ( b[i][v], b[i - 1][u] + c[i][v] ); setMax ( ans, b[i][v] ); } //printf ( "#%d ", ans ); } printf ( "%d ", ans );}void proc ()...{ dp (); //printf ( "%d ", len ); N = 0; memset ( b, 0x00, sizeof ( b ) );}void dfs ( int i, int n, int m )...{ if ( i == 15 ) ...{ trans[len].u = n, trans[len ++].v = m; return; } //printf ( "%d %d %d ", i, n, m ); int li = i - 1, hi = i + 1; if ( li >= 0 && n & p[li] || li >= 0 && m & p[li] || hi < 15 && n & p[hi] || n & p[i] ) dfs ( i + 1, n, m ); else ...{ dfs ( i + 1, n, m ); dfs ( i + 1, n, m | p[i] ); }}void checkAdj ()...{ len = 0; int i, j; for ( i = 0, j = 1; i < 15; i ++, j *= 2 ) p[i] = j; for ( i = 0; i < ( 1 << 15 ); i ++ ) ...{ if ( checkOne ( i ) ) dfs ( 0, i, 0 ); } printf ( "%d ", len );}int main ()...{ //freopen ( "in.txt", "r", stdin ); //freopen ( "out.txt", "w", stdout ); memset ( a, 0x00, sizeof ( a ) ); checkAdj (); //pt (); N = 0; while ( getline ( cin, str ) ) ...{ string t = str; if ( t == "" ) proc (); else init (); } return 0;}