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;
}

묘사

5
i
int
integer
intern
internet

4