首页 > 代码库 > Arthur and Brackets
Arthur and Brackets
n<605设计出n对夸号 给出n个条件每个条件为[l,r] 表示第i对夸号右夸号离左夸号的距离，然后夸号的右夸号出现的顺序必须按照给的顺序 出现， 那么如果存在就输出否则输出impossilbe ， 我们知道如果一个夸号在 L位置，那么 另一个夸号就在 L+cnt 这个位置， 那么我们就可以知道在L=1 和L+cnt-1 这之间的夸号只要合法就可以了
#include <iostream>#include <cstdio>#include<algorithm>#include <string.h>using namespace std;int dp[605][605],L[605],R[605];int get[605][605];int dfs(int l, int r){ if(dp[l][r]!=0) return dp[l][r]; if(l==r) return dp[l][r]=1; for(int k=L[l]; k<=R[l]; k+=2){ int left=k/2; if( left + l + 1 > r ) break; if(dfs(l+1,l+left+1)==1&&dfs(l+left+1,r)==1){ get[l][r]=left; return dp[l][r]=1; } } return dp[l][r]=2;}void print(int l, int r){ if(l==r) return ; printf("("); print(l+1,l+get[l][r]+1); printf(")"); print(l+get[l][r]+1,r);}int main(){ int n; while(scanf("%d",&n)==1){ memset(dp,0,sizeof(dp)); for(int i=0; i<n; ++i){ scanf("%d%d",&L[i],&R[i]); if(L[i]%2==0) L[i]++; } if(dfs(0,n)==1){print(0,n); printf("\n");} else puts("IMPOSSIBLE"); } return 0;}
#include <iostream>#include <cstdio>#include<algorithm>#include <string.h>using namespace std;int dp[605][605],L[605],R[605];int get[605][605];int dfs(int l, int r){ if(dp[l][r]!=0) return dp[l][r]; if(l==r) return dp[l][r]=1; for(int k=L[l]; k<=R[l]; k+=2){ int left=k/2; if( left + l + 1 > r ) break; if(dfs(l+1,l+left+1)==1&&dfs(l+left+1,r)==1){ get[l][r]=left; return dp[l][r]=1; } } return dp[l][r]=2;}void print(int l, int r){ if(l==r) return ; printf("("); print(l+1,l+get[l][r]+1); printf(")"); print(l+get[l][r]+1,r);}int main(){ int n; while(scanf("%d",&n)==1){ memset(dp,0,sizeof(dp)); for(int i=0; i<n; ++i){ scanf("%d%d",&L[i],&R[i]); if(L[i]%2==0) L[i]++; } if(dfs(0,n)==1){print(0,n); printf("\n");} else puts("IMPOSSIBLE"); } return 0;}
Arthur and Brackets
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。