HDU 4295 4 substrings problem(状态压缩)

/*内存超了，这道题原来不想做，后来打算只要把数据过了就行结果内存超了，状态压缩，具体思路参见：http://acmicpc.info/archives/915*/#include <cstdio>#include <cstring>const int INF = 4100;int d1[4096][16][64], d2[4100][16][64];char S[4100], a[4][70];int can[4100][4];int next[70];void getNext(char *s, int len){next[0] = -1;int i, j;for(i = 0, j = -1; i < len; ++ i){if(j == -1 || s[i] == s[j]){i ++;j ++;if(s[i] == s[j])next[i] = next[j];elsenext[i] = j;}elsej = next[j];}}void match(int c, char *S, char *s, int len_S, int len_s){int i, j;for(i = 0, j = 0; i < len_S;){if(j == -1 || S[i] == s[j]){i ++;j ++;if(j == len_s){can[i - len_s][c] = 1;i = i - len_s + 1;j = 0;}}elsej = next[j];}}int min(int a, int b){return a < b ? a : b;}int max(int a, int b){return a > b ? a : b;}int main(){//freopen("e://data.in", "r", stdin);int up = (1 << 4);while(scanf("%s%s%s%s%s", S, a[0], a[1], a[2], a[3]) != EOF){int i, j, k, l, m, kk;int len_S, len_a[4];len_S = strlen(S);for(i = 0; i < 4; ++ i)len_a[i] = strlen(a[i]);memset(can, 0, sizeof(can));for(i = 0; i < 4; ++ i){getNext(a[i], len_a[i]);match(i, S, a[i], len_S, len_a[i]);}int _max = 0, _min = 4100;memset(d1, -1, sizeof(d1));for(i = 0; i < 4096; ++ i)for(j = 0; j < 16; ++ j)for(k = 0; k < 64; ++ k)d1[i][j][k] = INF;memset(d2, -1, sizeof(d2));for(j = 0; j < 4; ++ j){if(can[0][j])d1[0][1 << j][len_a[j]] = d2[0][1 << j][len_a[j]] = len_a[j];}for(i = 1; i < len_S; ++ i){for(j = 0; j < 4; ++ j){if(can[i][j]){for(k = 0; k < up; ++ k){if(k & (1 << j)){kk = k;for(l = max(0, i - 64); l < i; ++ l){for(m = 0; m <= 64; ++ m){if(d1[l][k][m] != INF && l + m >= i)d1[i][k][len_a[j]] = min(d1[i][k][len_a[j]], d1[l][k][m]);if(d2[l][k][m] != -1 && l + m >= i)d2[i][k][len_a[j]] = max(d2[i][k][len_a[j]], d2[l][k][m]);}}}else{kk = (k | (1 << j));for(l = max(0, i - 64); l < i; ++ l){for(m = 0; m <= 64; ++ m){if(d1[l][k][m] != INF && l + m >= i)d1[i][kk][len_a[j]] = min(d1[i][kk][len_a[j]], d1[l][k][m] + len_a[j]);if(d2[l][k][m] != -1 && l + m >= i)d2[i][kk][len_a[j]] = max(d2[i][kk][len_a[j]], d2[l][k][m] + len_a[j]);}}}if(i + len_a[j] >= len_S){_min = min(_min, d1[i][kk][len_a[j]]);_max = max(_max, d2[i][kk][len_a[j]]);}}}}}printf("%d %d\n", _min, _max);}return 0;}