筱玛的网格

NC21819. 筱玛的网格

描述

筱玛是一个快乐的男孩子。

最近筱玛喜欢网格图，所以他想出了一个好玩的题。

网格图的每一个格子上都有字符 '(' 或 ')'。定义一个 n × m 的网格图是快乐的，当且仅当这个网格图满足任意一条从 (1, 1) 出发到 (n, m) 的最短路径都构成一个合法的括号序列。

筱玛对每一个格子 (i, j) 都有一个互不相同的喜爱程度 val[i][j]。

对于任意一个快乐网格图，按照喜爱程度从小到大将格中字符依次写下，可以得到一个字符串。

他希望得到一个网格图，使得其对应的字符串在所有 n × m 的快乐网格图对应的字符串中字典序第 k 小。

其中 '(' 的字典序小于 ')'。

下面我们给出括号序列的定义：

空序列是合法的括号序列；
如果 S 是合法括号的序列，那么 (S) 也是合法的括号序列；
如果 A 和 B 都是合法的括号序列，那么 AB 也是合法的括号序列。

输入描述

输入共 n + 1 行。
第一行三个整数分别表示 n, m, k。
接下来 n 行，每行 m 个整数，表示 val[i][j]。
保证 n + m - 1 是偶数。
保证快乐网格图总数 ≥ k。

输出描述

输出共 n 行，每行一个字符串，长度为 m。
表示对应字符串字典序第 k 小的网格图。

示例1

输入:

输出:

(()
()(
)()
())

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 1440K, 提交时间: 2020-08-04 14:12:29

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,y,w;
}R[40005];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
    int i,j,k,n,m,t,L=0,V[405],DP[405][405];
    char ans[205];
    scanf("%d%d%d",&n,&m,&t);
	for(i=1;i<=n;i++)
    	for(j=1;j<=m;j++)scanf("%d",&R[L].w),R[L].x=i,R[L++].y=j;
    sort(R,R+L,cmp);
    for(i=0;i<L;i++)
    {
    	if(V[R[i].x+R[i].y])continue;
    	V[R[i].x+R[i].y]=-1;
    	memset(DP,0,sizeof(DP)),DP[1][0]=1;
    	for(j=2;j<=n+m;j++)
    	{
    		if(!V[j])for(k=0;k<=j;k++)DP[j][k]=min(DP[j-1][k+1]+(!k?0:DP[j-1][k-1]),1000000007);
			else if(V[j]==1)for(k=0;k<=j;k++)DP[j][k]=DP[j-1][k+1];
			else for(k=1;k<=j;k++)DP[j][k]=DP[j-1][k-1];
		}
    	if(DP[n+m][0]<t)V[R[i].x+R[i].y]=1,t-=DP[n+m][0];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(V[i+j]==-1)ans[j]='(';
			else ans[j]=')';
		}
		printf("%s\n",ans+1);
	}
    return 0;
}