poj1068

1402 단어 알고리즘
간단 한 아 날로 그 문제 의 대의: 제 시 된 원 괄호 문자열 에 대해 두 가지 숫자 암호 문자열 이 존재 합 니 다. 1. p 시퀀스: 괄호 와 일치 하 는 쌍 이 나타 날 때 이 괄호 의 오른쪽 괄호 부터 왼쪽으로 세 고 맨 앞 에 있 는 왼쪽 괄호 까지 는 p [i] 의 값 입 니 다.2. w 시퀀스: 일치 하 는 괄호 쌍 이 나타 날 때 이 괄호 쌍 에 포 함 된 모든 오른쪽 괄호 수 (이 괄호 쌍 포함) 는 w [i] 의 값 입 니 다.제 시 된 p 숫자 문자열 에 대응 하 는 s 문자열 을 구 합 니 다.직렬 길이 제한 모두 20
코드 는 다음 과 같 습 니 다:
//     +                    
public class Main_1068
{
	static int n;
	static int[] p=new int[21];
	static int[] w=new int[21];
	
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		int k=in.nextInt();
		
		while(k-->0)
		{
			n=in.nextInt();
			for(int i=1;i<=n;i++)
			{
				p[i]=in.nextInt();
			}
			
			solve();
		}
	}
	
	static int[] s=new int[10000];//s[i]=0:    i    ,s[i]=1    i    
	static int cnt=0;
	static void solve()
	{
		// p        
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=p[i]-p[i-1];j++)//p[i]-p[i-1]: i      i-1           
			{
				s[cnt++]=1;
			}
			s[cnt++]=0;
		}
		
		int t=0;int tmp=0;int pos=0;
		for(int i=0;i=0;j--)
				{
					if(s[j]==1)
					{
						s[i]=s[j]=2;//       ,         
						pos=j;
						break;
					}
				}
				//                    
				for(int k=i;k>=pos;k--)
				{
					if(s[k]==2)
					{
						tmp++;
					}
				}
				w[t++]=tmp/2;
			}
		}
	
		for(int i=0;i

좋은 웹페이지 즐겨찾기