记忆化搜索。在表达篮子里糖果的状态时采取位操作。
记录f(x1,x2,x3,x4)代表当第i列娶到xi个时的最大糖果数量。然后……强搜吧，没什么好说的。也许还可以剪枝，但时限在暴力搜索面前都不堪一击。
位操作是相当有趣的hash方法，我得好好练习一下。
#include <cstdio>#include <string>int a[40][4], f[41][41][41][41], N, b[5], h[5], x[4], ans;void dp ();void dfs ( int, int );void pb ();int main ()
...{
//freopen ( "in.txt", "r", stdin ); while ( scanf ( "%d", &N ) && N )
...{ int i, j; for ( i = 0; i < N; i ++ ) ...{ for ( j = 0; j < 4; j ++ ) scanf ( "%d", &a[i][j] );
} dp (); printf ( "%d ", ans / 2 ); } return 0;
}void dp ()...{ ans = 0; h[0] = 31; int i; for ( i = 1; i < 5; i ++ ) h[i] = h[i - 1] << 5; memset ( f, 0xff, sizeof ( f ) ); memset ( x, 0, sizeof ( x ) ); f[0][0][0][0] = 0; dfs ( 0, 0 );}void dfs ( int hash, int num )...{ int i, k, t, full, thash = hash, tnum = num; full = 1; for ( i = 0; i < 5; i ++ ) ...{ t = hash & h[i]; b[i] = t >> ( 5 * i ); if ( !b[i] ) full = 0; } //pb (); if ( full ) return; for ( k = 0; k < 4; k ++ ) ...{ if ( x[k] < N ) ...{ int get = 0; for ( i = 0; i < 5; i ++ ) ...{ if ( a[x[k]][k] == b[i] ) ...{ hash = hash & ( ~h[i] ); num += 2; get = 1; break; } } if ( !get ) ...{ for ( i = 0; i < 5; i ++ ) ...{ if ( !b[i] ) ...{ hash = hash | ( a[x[k]][k] << ( 5 * i ) ); break; } } } x[k] ++; if ( f[x[0]][x[1]][x[2]][x[3]] < num ) ...{ f[x[0]][x[1]][x[2]][x[3]] = num; if ( num > ans ) ans = num; dfs ( hash, num ); } hash = thash, num = tnum; x[k] --; for ( i = 0; i < 5; i ++ ) ...{ t = hash & h[i]; b[i] = t >> ( 5 * i ); } //pb (); } }}