Parentheses Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 728 Accepted Submission(s): 294
Special Judge
- an empty sequence is balanced;
- if A is balanced, then (A) is also balanced;
- if A and B are balanced, then AB is also balanced.
For example, the following parentheses matrix is a 2×4 matrix with goodness 3, because the second row, the second column and the fourth column are balanced:
)()(
()()
Now, give you the width and the height of the matrix, please construct a parentheses matrix with maximum goodness.
Each test case is a single line of two integers h,w (1≤h,w≤200), the height and the width of the matrix, respectively.
这题。。。。WA到死啊 在h=2那里摔倒了好几次都没看出来
题意是构造一个 h×w 的括号矩阵，并且使其匹配的行数、列数之和最大的矩阵之一。
当 h 和 w 中有一个是奇数时，构造的方法是显然的。下面仅讨论 h 和 w 都是偶数的情况。不妨设 h≤w。 首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考虑右上角和左下角的括号选取方法），故答案不会超过 w+h−2。
当 h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。 当 h = 4 时，可以如下构造：
((((((
)))(((
((()))
))))))
这样答案是 w+h−3。若存在更优的答案，则必有一个边界能够匹配，不妨设是第一列。这样，就已 经有除第一行以外的两行（右括号开头的行）不匹配了，而第一行和最后一列中至少有一个不匹配， 因此最优解不会超过 w+h−3。
当 h≥6 时，可以如下构造：
((((((((
()()()()
(()()())
()()()()
(()()())
))))))))
答案是 w+h−4。同理可证明不存在更优的方法。
#include <iostream> using namespace std; int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int h, w;
cin >> h >> w; if (h % && w % )
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j++)
cout << "(";
cout << endl;
}
}
else if (!(h % ) && w % )
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j++)
{
if (i % )
cout << ")";
else
cout << "(";
}
cout << endl;
}
}
else if (!(w % ) && h % )
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j++)
{
if (j % )
cout << ")";
else
cout << "(";
}
cout << endl;
}
}
else if (w == || h == )
{
if (w >= h)
{
for (int j = ; j < w; j++)
cout << "(";
cout << endl;
for (int j = ; j < w; j++)
cout << ")";
cout << endl;
}
else
{
for (int i = ; i < h; i++)
cout << "()" << endl;
}
}
else if (w == || h == )
{
if (w >= h)
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j++)
{
if (!i)
cout << "(";
else if (i == )
{
if (j < w / )
cout << "(";
else
cout << ")";
}
else if (i == )
{
if (j >= w / )
cout << "(";
else
cout << ")";
}
else
cout << ")";
}
cout << endl;
}
}
else
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j += )
{
if (i < h / )
cout << "()";
else
{
if (j < w / )
cout << "((";
else
cout << "))";
}
}
cout << endl;
}
}
}
else
{
for (int i = ; i < h; i++)
{
for (int j = ; j < w; j++)
{
if (!i)
cout << "(";
else if (i == h - )
cout << ")";
else if (i % == )
{
cout << "()";
j++;
}
else if (i % )
{
if (!j)
cout << "(";
else if (j == w - )
cout << ")";
else
{
cout << "()";
j++;
}
}
}
cout << endl;
}
}
} return ;
}