zoj1425Crossed Matchings

와글와글또 A를 했다.
방금 쓴 건데 너무 설레요.
오후에 제목을 봤는데 제목은 두 줄의 숫자로 되어 있고 위아래와 같은 숫자의 연결선이 한 번에 일치하는 것을 계산하여 가능한 최대 일치를 구했다. 규칙은 I연결선은 반드시 다른 직선으로만 통과해야 한다는 것이다.그리고 이 두 직선이 대표하는 숫자는 같을 수 없다.II 숫자는 하나의 연결선만 있을 수 있다.
처음에는 별 생각이 없었고 dp도 생각했지만 구체적으로 어떻게 실현될지 몰랐어요.
저녁에 다시 자세히 보니 dp는 만들 수 있을 것 같아서 for순환을 많이 썼지만 제 생각대로 이해하면 간단할 것 같습니다.
pp[i][j]는 첫 번째 줄의 숫자가 i부터 n까지, 두 번째 줄의 숫자가 j에서 m까지 몇 개가 일치하는지 나타낸다.
dp[i][j-1]에 대해 b[j-1]과 첫 줄의 a[i]만 토론하면...a[n]의 일치 상황.
코드 보기:

# include<stdio.h>

# include<string.h>

int a[105],b[105],n,m,dp[105][105];

int main()

{

	int i,j,t,k,h,s,flag,max;

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&n,&m);

		for(i=1;i<=n;i++)

			scanf("%d",&a[i]);

		for(j=1;j<=m;j++)

			scanf("%d",&b[j]);

		for(j=1;j<=m;j++)

		{

			dp[n][j]=0;

			dp[n+1][j]=0;

		}

		for(i=1;i<=n;i++)

		{

			dp[i][m]=0;

			dp[i][m+1]=0;

		}

		dp[n+1][m+1]=0;/*    ,            wa    */

		for(i=n-1;i>=1;i--)

			for(j=m-1;j>=1;j--)

			{

				max=dp[i][j+1];/*       b[j]     */

				for(k=i+1;k<=n;k++)

				{

					if(b[j]==a[k]) 

					{

						flag=0;

						for(h=j+1;h<=m;h++)

						{

							if(b[h]==b[j]) continue;/*            */

							for(s=i;s<k;s++)

							{

								if(b[h]==a[s]) {flag=1;break;}

							}

							if(flag==1) break;

						}

						if(flag==1) 

						{

							if(max<dp[k+1][h+1]+2) max=dp[k+1][h+1]+2;/*        */

						}

					}

				}

				dp[i][j]=max;

			}

			printf("%d
",dp[1][1]);

	}

	return 0;

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

VBA에서 Match 함수를 사용하여 열 번호 얻기

Excel 시트에서는 열을 추가하거나 삭제할 수 있습니다. 아래와 같은 코드라면 그때 다시 쓰게 되기 때문에 그때 다시 쓰지 않아도 좋다 항목 행에서 항목 이름을 Match 함수로 검색하여 변수에 저장합니다. 실행 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

zoj1425Crossed Matchings

좋은 웹페이지 즐겨찾기