vijos P1028 마족 비밀번호 DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool judge(const string &aa,const string &bb)
{
	for(int i=0;i<bb.size();++i)
	{
		if(bb[i]!=aa[i])
			return 0;
	}
	return 1;
}
int main()
{
	//freopen("i.txt","r",stdin);
	//freopen("o.txt","w",stdout);
	int dp[20000];
	vector<string>q;
	string s;int n;
	cin>>n;
	map<string,int>p;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		q.push_back(s);
		p[s]=i;
	}
	vector<string>::iterator it;
	int ans=-1;
	for(it=q.begin();it!=q.end();it++)
	{
		dp[p[*it]]=1;
		for(vector<string>::iterator j=q.begin();j!=it;j++)
		{
			if(it->size()>j->size())
			{
				if(judge(*it,*j)&&dp[p[*it]]<dp[p[*j]]+1)
					{
						dp[p[*it]]=dp[p[*j]]+1;
					}
			}
		}
		if(ans<dp[p[*it]])
			ans=dp[p[*it]];
	}
	printf("%d
",ans);
	return 0;
}

이 문제는 가장 긴 상승 서열의 변형입니다. 그러나 이것은 문자열 처리입니다.이 문제를 해결하고 STL 지식도 많이 배웠습니다.RE를 한 번 하고서야 dp수 그룹이 작아진 것을 발견하였다.여기에서 나는find 함수를 사용하려고 했지만 왜 안 되는지 몰라서judge 함수를 하나 썼다.지나고 보니 9조 테스트 데이터밖에 없어요. 이거 너무 적은 거 아니에요...
P1028 마족 비밀번호
Accepted
태그:[태그 표시]

묘사

바람둥이가 고사장에 들어서자마자...꽃:당당당~~ 우연히 매력퀸-꽃!!^^(화려하게 등장, 예포, 꽃) 바람의 아들: ...(사람을 죽이는 눈빛) 빨리 제목을 말해!그렇지 않으면...- -###꽃:...어~~ 추워~~ 우리가 지금 해결해야 할 것은 마족의 비밀번호 문제야.마족은 현재 신형 암호 시스템을 사용하고 있다.모든 암호는 소문자만 포함하는 영문 단어표로 정해져 있으며, 단어마다 적어도 한 글자에서 75글자까지 포함된다.만약 한 단어나 여러 단어로 구성된 표에서 마지막 단어를 제외하고는 모든 단어가 그 뒤의 한 단어에 포함된다. 즉, 앞의 단어가 뒤의 단어의 접두사라면 어표를 하나의 어체인이라고 한다.예를 들어 아래의 단어는 하나의 단어 체인을 구성한다. i int integer이지만 아래의 단어는 단어 체인을 구성하지 않는다. integer intern은 현재 당신이 해야 할 일은 주어진 단어표에서 몇 개의 단어를 꺼내서 가장 긴 단어 체인을 구성하는 것이다. 바로 단어 수가 가장 많은 단어 체인을 포함하는 것이다.그것의 단어 수를 통계하면 비밀번호를 얻을 수 있다.
바람의 아들: 비밀번호는 가장 긴 단어 체인에 포함된 단어 수야...꽃:살아있다, 그리고 이 파일들의 형식은 첫 번째 행동 단어표에 있는 단어 수 N(1<=N<=2000)이다. 아래 줄마다 단어가 하나 있는데 사전 순서대로 배열되어 있고 중간에 반복되는 단어도 없다!!당신이 제출할 파일에는 첫 줄에 비밀번호만 출력하면 됩니다^^ 잘 생긴 것 같으니 예시를 하나 드릴게요.

예제 1

샘플 입력 1[복사]

5
i
int
integer
intern
internet

샘플 출력 1[복사]

제한

각 테스트 포인트 1s

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

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

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

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

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

vijos P1028 마족 비밀번호 DP

묘사

예제 1

샘플 입력 1[복사]

샘플 출력 1[복사]

제한

좋은 웹페이지 즐겨찾기