Problem H. Password Service
题目连接：
http://www.codeforces.com/gym/100253
Description
Startups are here, startups are there. Startups are everywhere! Polycarp would like to have his own
startup, too. His business idea is a password service. Have you noticed how many hours you spent trying
to create a password?
Polycarp's service will help clients to create a password by requirements. He is thinking about a freemium
business model of monetization. He doesn't know what it is, but he likes the word freemium.
The rst release of Polycarp's startup should have a simple form with two elds. The rst eld is for n,
where n denotes that the required password can consist of only rst n lowercase letters from the Latin
alphabet. The second form eld is for string s containing the characters <', >' and `='. The sign in position
i denotes the comparison result of the i-th and the (i + 1)-th character in the password. So if the length
of s is l then the required password should consist of exactly l + 1 lowercase letters.
Polycarp oers you a great position in his startup, he oers you to become the CTO. Polycarp can't oer
you a great salary (just only $1), but he will give you so many stock options that in case of IPO exit
you will be a millionaire! Why not? So your task is to write a program to generate a password containing
some of the rst n lowercase letters of the Latin alphabet and which has s as a result of comparisons of
consecutive characters
Input
The rst line of the input contains an integer number n (1 ≤ n ≤ 26), where n denotes that the required
password should contain only lowercase letters from the rst n letters of the Latin alphabet. The second
line contains the string s (the length of s is between 1 and 5000, inclusive), where s consists of the
characters <', >' and `='. The i-th character stands for the result of comparison of the i-th and the
(i + 1)-th characters of the password.
Output
Print the required password or -1 if it doesn't exist. You may print any answer in case of multiple answers.
Sample Input
5
=<>
Sample Output
bbdc
Hint
题意
给你一个字符串，你可以用n个字符。
要求满足字符串所给的大小关系表示。
题解：
dp，dp[i][j]表示第i个位置用第j个字符可不可行。
然后转移就行了。
其实贪心好像也可以，懒得去想了……
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
char s[maxn];
int p[maxn][26];
pair<int,int> re[maxn][26];
int N,n;
vector<int>ans;
void dfs(int x,int y,int rx,int ry)
{
if(p[x][y])return;
p[x][y]=1;
re[x][y]=make_pair(rx,ry);
if(x==n)return;
if(s[x+1]=='=')
dfs(x+1,y,x,y);
if(s[x+1]=='<')
{
for(int j=y+1;j<N;j++)
dfs(x+1,j,x,y);
}
if(s[x+1]=='>')
{
for(int j=y-1;j>=0;j--)
dfs(x+1,j,x,y);
}
}
int flag = 0;
void dfs2(int x,int y)
{
if(flag)return;
if(re[x][y].first==-1)
{
flag = 1;
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
printf("%c",ans[i]+'a');
}
printf("
");
return;
}
ans.push_back(re[x][y].second);
dfs2(re[x][y].first,re[x][y].second);
}
int main(){
scanf("%d",&N);
scanf("%s",s+1);
n = strlen(s+1);
for(int i=0;i<N;i++)
dfs(0,i,-1,-1);
for(int i=0;i<N;i++)
{
if(p[n][i])
{
ans.push_back(i);
dfs2(n,i);
ans.pop_back();
return 0;
}
}
if(!flag)printf("-1");
}