C. Playing Piano 动态规划

时间：2022-04-23 04:08:17

题目意思是给你一个n长度的数字串为a，让你构造一个n长度的数字串b值都为1-5满足以下条件：

C. Playing Piano 动态规划

正常的dfs暴力构造会超时，我试过了。。

可以开一个二维数组dp[i][j]用来表示b的第i个数字为j是否可行，标记为1或0；

因为第i个数字的大小只会影响第i+1个数字，每次确定i都根据第i-1的数字来判断。

再开一个二维数组pre[i][j]用来表示b的第i个 数字为j时的前一个数字是多少，最后倒推时用stack记录一下输出答案；

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

int a[maxn];

int dp[maxn][];

int pre[maxn][];

stack<int> s;

int main()

{

    int n;

    scanf("%d", &n);

    for(int i=; i<=n; i++)

        scanf("%d", &a[i]);

    for(int i=; i<=; i++)

        dp[][i]=;

    for(int i=; i<=n; i++)

        for(int j=; j<=; j++)

        {

            if(dp[i-][j]==)

                continue;

            if(a[i]>a[i-])

            {

                for(int k=j+; k<=; k++)

                {

                    dp[i][k]=;

                    pre[i][k]=j;

                }

            }

            if(a[i]<a[i-])

            {

                for(int k=j-; k>=; k--)

                {

                    dp[i][k]=;

                    pre[i][k]=j;

                }

            }

            if(a[i]==a[i-])

            {

                for(int k=; k<=; k++)

                    if(k!=j)

                    {

                        dp[i][k]=;

                        pre[i][k]=j;

                    }

            }

        }

    for(int i=; i<=n; i++)

    {

        for(int j=; j<=; j++)

            printf("%d ", pre[i][j]);

        printf("\n");

    }

    int t=;

    for(int j=; j<=; j++)

    {

        if(dp[n][j]==)

            t=j;

    }

    if(t==)

    {

        printf("-1");return ;

    }

    for(int i=n; i>=; i--)

    {

        s.push(t);

        t=pre[i][t];

    }

    while(!s.empty())

    {

        printf("%d ", s.top());

        s.pop();

    }

}

相关文章