欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 6400 Parentheses Matrix

程序员文章站 2024-02-24 15:10:12
...

题目:点击打开链接
题意: 给一个只含'('和')'的矩阵,只考虑从行和列上的括号序列,构造一个矩阵使得合法括号序列的总数最多。

分析:构造,分类讨论。首先奇数行或奇数列内是不存在合法括号序列的,所以如果n或m是奇数,则最多有n/m个括号序列(即把行/列直接填充为合法序列),需要分析的是偶数行和偶数列的情况。
首先贪心一下,起点位于第一行和第一列,所以应该尽量在这些位置填'(',首先想到的是把矩形的左上边界填充为'(',右下边界填充为')'

.((((.
(....)
(....)
(....)
(....)
.)))).


因为第一行,第n行,第1列,第m列一定不是序列,所以这样最多有n+m-4个合法括号序列。

但有一个情况比较特殊,当n=4的时候,上面的方法其实比较亏,以牺牲第一列和最后一列的代价,却只得到了两行合法括号序列。考虑另外一种填充方法:当n比较小的时候,把第一行全部填充为'(',最后一行全部填充为')'

((((((
......
......
))))))


这样以后发现,可以通过调整剩下的位置,让剩下一半的行数成为合法的序列,于是这样最多有(n-2)/2+m=n/2-1+m个合法括号序列
比较一下上面两种方案,假设a>b,当第一种最多a+b-4,第二种最多a+b/2-1,当他们相等时,a+b-4=a+b/2-1,解得b=6,也就是行数列数最小值小于6的时候,应该采用第二种方案能获得更多,而其他情况应该选择第一种情况

代码:

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
typedef pair<int,int> PII;
const ll mod = 1e9+7;
const int N = 1e6+10;

ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int t,h,w;
char s[300][300];

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>t;
    while(t--) {
        cin>>h>>w;
        int rev=0;
        if(h&1) {
            if(w&1) {
                rep(i,1,h) rep(j,1,w) s[i][j]='(';
            }else {
                rep(i,1,h) rep(j,1,w)
                        if(j&1) s[i][j]='(';
                        else s[i][j]=')';
            }
        }else {
            if(w&1) {
                rep(i,1,h) rep(j,1,w)
                        if(i&1) s[i][j]='(';
                        else s[i][j]=')';
            }else {
                if(h>w) {
                    rev=1;
                    swap(h,w);
                }
                if(h==2) {
                    rep(i,1,w) s[1][i]='(',s[2][i]=')';
                }else if(h==4) {
                    rep(i,1,w) {
                        s[1][i] = '(';
                        s[2][i] = i>w/2 ? '(' : ')';
                        s[3][i] = i>w/2 ? ')' : '(';
                        s[4][i] = ')';
                    }
                }else {
                    rep(i,1,w) s[1][i]='(',s[h][i]=')';
                    rep(i,2,h-1) {
                        if(i&1) {
                            s[i][1]='(',s[i][w]=')';
                            rep(j,2,w-1) s[i][j]='(',j++,s[i][j]=')';
                        }else {
                            rep(j,1,w) s[i][j]='(',j++,s[i][j]=')';
                        }
                    }
                }
            }
        }
        if(rev) {
            rep(i,1,w) {
                rep(j,1,h) cout<<s[j][i];
                cout<<endl;
            }
        }else {
            rep(i,1,h) {
                rep(j,1,w) cout<<s[i][j];
                cout<<endl;
            }
        }
    }
    return 0;
}

参考博客:http://www.cnblogs.com/tobyw/p/9483865.html