Password Service

Bize L uzunluğunda <,>,= işaretlerinden oluşan S stringi veriliyor. Bizden istenen alfabenin ilk N harfini kullanarak L+1 uzunluğunda bir string oluşturmamız.

Oluşturmamız gereken str stringi şöyle olmalıdır...
S[i] = '<' ise str[i]<str[i+1]
S[i] = '>' ise str[i]>str[i+1]
S[i] = '=' ise str[i]=str[i+1]

Eğer bu koşulları sağlayan bir string yoksa -1 yazdırınız.

Input Format
İlk satırda N: Alfabenin ilk N harfini(küçük harf) kullanabiliyoruz.
2. satırda S: Oluşturmamız istenen str için gerekli koşulları içerir.

Output Format
Koşulları sağlayan stringi yazdırınız. Yoksa -1 yazdırın.

Constraints
1 <= N <= 26
1 <= L <= 5000

Input
5
=<>

Output
bbdc

_____________________________

Link

Soru: http://codeforces.com/gym/100253 (H sorusu)
pdf: http://codeforces.com/gym/100253/attachments/download/1971/20132014-acmicpc-neerc-southern-subregional-contest-en.pdf
_____________________________

Çözüm

Bu soru ilkin greedy gibi gözükse de aslında DP sorusudur.

DP[curr][c] : Şu anki pozisyonumuz curr, son karakterimiz c olsun. Bundan sonra yapmamız gereken S stringindeki kurallara göre yeni karakter eklemek.

Her mümkün (curr,c) durumu için eklenmesi gereken karakteri tutarız. Stringi yazdırırken bunu kullanacağız.
_____________________________

Kodum

#include <algorithm>
#include <string.h>
#include <stdio.h>
#define  maxc      26
#define  maxn      5004
using    namespace std;

int n,len;
char s[maxn];
int dp[maxn][maxc];
int best[maxn][maxc];

int f(int curr , int c)
{
  if(curr==len+1)  return 1;
  if(dp[curr][c])  return dp[curr][c];
  if(s[curr]=='=')
  {
    if(f(curr+1,c)==1)
    {
      best[curr][c]=c;
      return dp[curr][c]=1;
    }
  }
  if(s[curr]=='<')
  {
    for(int i=c+1 ; i<n ; i++)
      if(f(curr+1,i)==1)
      {
        best[curr][c]=i;
       return dp[curr][c]=1;
      }
  }
  if(s[curr]=='>')
  {
    for(int i=0 ; i<c ; i++)
      if(f(curr+1,i)==1)
      {
        best[curr][c]=i;
       return dp[curr][c]=1;
      }
  }
  return dp[curr][c]=2;
}

void Write(int x)
{
  printf("%c",x+'a');
  for(int i=1 ; i<=len ; i++)
  {
    x=best[i][x];
    printf("%c",x+'a');
  }
  printf("\n");
}

int main()
{
  scanf("%d%s",&n,s+1);
  len=strlen(s+1);
  bool ok=false;
  for(int i=0 ; i<n ; i++)
    if(f(1,i)==1)
    {
      Write(i);
      ok=true;
      break;
    }
  if(!ok) printf("-1\n");
  return 0;

}