简明题意：用a个0，b个1构建出长度为n=a+b的字符串s，且对于$0 < i < n$，有$s_i != s_{i-1}$的i的个数恰为x。
当时比赛的时候没做出来，估计就是要写搜索一类的就先跳过了。后来再来写这道题目。
所以今天改了三遍。没有看任何题解。第一版：递归，第二版：递推/迭代（动规），第三版：递推（动规）+滚动数组优化。真的不知道我是怎么想起来N长时间之前背包问题里的滚动数组优化了。感觉自己特别厉害好长时间都没写了这都能想的起来。第三版程序终于有了让人没有文字说明就完全看不懂想不明白的资本啦，哈哈^v^
第一版：递归，没有任何记忆化措施，所以TLE了，然后就想着把递归换成递推。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include<iostream> #include<algorithm> using namespace std; int a, b, x; char str[105]; bool recusive(int curpos, int cura, int curb, int curx) { if (curpos == a + b) { if (cura == a && curb == b && curx == x) { str[curpos] = '\0'; return true; } else return false; } if ((cura == a || curb == b)&&curx==x) { if (cura == a) { for (int i = curpos; i < a + b; i++)str[i] = '1'; str[a + b] = '\0'; return true; } else { for (int i = curpos; i < a + b; i++)str[i] = '0'; str[a + b] = '\0'; return true; } } //Assume curpos==0 str[curpos] = '0'; bool flag = false; if (curpos == 0 || str[curpos - 1] == '0')flag = recusive(curpos + 1, cura + 1, curb, curx); else flag = recusive(curpos + 1, cura + 1, curb, curx + 1); if (flag)return true; str[curpos] = '1'; if (curpos == 0 || str[curpos - 1] == '1')flag = recusive(curpos + 1, cura, curb + 1, curx); else flag = recusive(curpos + 1, cura, curb + 1, curx + 1); if (flag)return true; return false; } int main() { cin >> a >> b >> x; recusive(0, 0, 0, 0); cout << str; } |
第二版：递推。没有任何优化，时间够了，但是内存不够MLE了。四个维度分别是a,b,x,上个字符串的最后一个数字是0还是1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include<iostream> #include<algorithm> #include<string> using namespace std; int a, b, x; string arr[101][101][201][2]; //a,b,x, int main() { cin >> a >> b >> x; for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0'; for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1'; for (int k = 1; k <= x; k++) { //curx for (int i = 1; i <= a; i++) { //cura for (int j = 1; j <= b; j++) { //curb //Assume to place a 0 if (arr[i - 1][j][k - 1][1] != "")arr[i][j][k][0] = arr[i - 1][j][k - 1][1] + '0'; else if (arr[i - 1][j][k][0] != "")arr[i][j][k][0] = arr[i - 1][j][k][0] + '0'; //Assume to place a 1 if (arr[i][j - 1][k - 1][0] != "")arr[i][j][k][1] = arr[i][j - 1][k - 1][0] + '1'; else if (arr[i][j - 1][k][1] != "")arr[i][j][k][1] = arr[i][j - 1][k][1] + '1'; } } } if (arr[a][b][x][0] != "")cout << arr[a][b][x][0]; else cout << arr[a][b][x][1]; } |
第三版：递推+滚动数组。把第三维由201优化到只剩2。因为动规的转移方程里面只需要上一个k和当前k的数组，所以滚动数组优化一下就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include<iostream> #include<algorithm> #include<string> using namespace std; int a, b, x; string arr[101][101][2][2]; inline int trans(int num) { if (num % 2 == 0)return 0; else return 1; } int main() { cin >> a >> b >> x; for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0'; for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1'; for (int k = 1; k <= x; k++) { //curx for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)for(int m=0;m<=1;m++)arr[i][j][trans(k)][m]=""; //Clean the rolling array to prevent unexpected error for (int i = 1; i <= a; i++) { //cura for (int j = 1; j <= b; j++) { //curb //Assume to place a 0 if (arr[i - 1][j][trans(k - 1)][1] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k - 1)][1] + '0'; else if (arr[i - 1][j][trans(k)][0] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k)][0] + '0'; else arr[i][j][trans(k)][0]=""; //Assume to place a 1 if (arr[i][j - 1][trans(k - 1)][0] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k - 1)][0] + '1'; else if (arr[i][j - 1][trans(k)][1] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k)][1] + '1'; else arr[i][j][trans(k)][1]=""; } } } if (arr[a][b][trans(x)][0] != "")cout << arr[a][b][trans(x)][0]; else cout << arr[a][b][trans(x)][1]; } |
写了我三个小时，也是挺不容易的……继续努力！写的不清楚有问题可以在下面评论问。