2018 女生赛--HDU - 6294（简单dp）

2018 女生赛--HDU - 6294（简单dp）

一开始暴力了一发 ， 果然不对

原来是dp啊

题意：

给你一个长度为n的字符串 s1 ,

令X = s1[i.....n]

Y = s1[i+1.....n]

输出n-1个答案 ， 判断X和Y的字典序大小

题目给了俩个条件：

1. 如果Y的长度为k 并且 X的前k个和Y相等 ， 那么X大
2. 如果Y的长度大于k 并且 X的前k个和Y的前k个相等 那么判断k+1的X和Y的大小

举个例子：

S1： x1x2x3x4x5;

那么

1.   x1 x2 x3 x4 x5

           x2 x3 x4 x5

1.   X2 x3 x4 x5

            X3 x4 x5

1.   X3 x4 x5

           X4 x5

1.   X4 x5

           X5

很明显发现若求1时 ， 只要比较x1 和x2 就行 ， 如果相等就可以直接调用2的答案，同理下面

那么可以倒着求

令dp[i][j] = 0 表示s1>s2 , dp[i][j]=1 表示小于 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+8;
int dp[maxn];
int main()
{
    int t , n;
    char str[maxn];
    scanf("%d" , &t);
    while(t--)
    {
        memset(dp , -1 , sizeof(dp));
        scanf("%d" , &n);
        scanf("%s" , &str);
        if(str[n-1] <= str[n-2])dp[n-1] = 0;
        else dp[n-1] = 1;
        for(int i = n-2 ; i > 0 ; i--)
        {
            if(str[i] > str[i-1])
            {
                dp[i] = 1; 
            }
            else if(str[i] < str[i-1])
            {
                dp[i] = 0;
            }
            else
            {
                dp[i] = dp[i+1];
            }
        }
        for(int i = 1 ; i < n ; i++)
        {
         //   printf("%d " , dp[i]);
            if(dp[i] == 0)
            printf(">");
            if(dp[i] == 1)
            printf("<");
        }
        printf("\n");
    }
    return 0;
}