【HDU6357】Hills And Valleys（DP）

题意

给定一个数组A[]，元素均在[0,9]，可以翻转一段区间，求最长不下降子序列，并输出翻转区间

题解

很巧妙的DP

因为值域很小，我们可以枚举需要翻转的区间值出一个数组B[]，规划好我们要求得的序列的大致趋向。
如我们翻转的区间的值为[7,3]，则构建B数组为B[]={0,1,2,3,7,6,5,4,3,7,8,9}，dp时按照B数组中的元素，进行转移。

定义dp状态：dp[i][j]为匹配到A串的第i位，B串的第j位，最长不下降子序列的长度：
转移为dp[i][j] = min ( dp[i][j-1], dp[i-1][j]+(A[i]==B[j]) )
从dp[i][j-1]转移是为了保证j越大，dp[i][j]也越大，使得当i固定，dp[i][j]保持不下降
从dp[i-1][j]转移即在A串中添加一位A[i]，如果A[i]值在匹配的B串位置之后，则最长不下降序列可增加一位，因为我们已经保证dp[i][j]>=dp[i][j-1]，所以只用判断A[i]==B[j]即可。

因为需要输出翻转方案，我们用path[i][j]数组记录dp转移路径，dp完成后，利用path恢复我们从B中选出来的元素（作为最长不下降子序列的元素），存在数组C[i]里，然后判断从哪一位开始翻转即可。
注意：如果没有翻转，需把翻转区间长度设为1（自己跟自己翻转）

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005,MAXL=33;

int N,M;
int A[MAXN],B[MAXL];
int dp[MAXN][MAXL];
pair<int,int> path[MAXN][MAXL],C[MAXN];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
            scanf("%1d",&A[i]);
        int ans=0,ansl,ansr;
        for(int x=0;x<10;x++)
            for(int y=x;y<10;y++)
            {
                M=0;
                int l,r;
                for(int i=0;i<=x;i++)
                    B[++M]=i;
                l=M+1;
                for(int i=y;i>=x;i--)
                    B[++M]=i;
                r=M;
                for(int i=y;i<10;i++)
                    B[++M]=i;
                for(int i=1;i<=N;i++)
                    for(int j=1;j<=M;j++)
                    {
                        if(dp[i][j-1]<dp[i-1][j]+(A[i]==B[j]))
                        {
                            dp[i][j]=dp[i-1][j]+(A[i]==B[j]);
                            path[i][j]=make_pair(i-1,j);
                        }
                        else
                        {
                            dp[i][j]=dp[i][j-1];
                            path[i][j]=make_pair(i,j-1);
                        }
                    }
                if(dp[N][M]>ans)
                {
                    ans=dp[N][M];
                    int p=N,q=M,top=ans;
                    ansl=-1,ansr=-1;
                    pair<int,int> t;
                    while(p&&q)
                    {
                        t=path[p][q];
                        if(dp[t.first][t.second]+1==dp[p][q]&&A[p]==B[q])
                            C[top--]=make_pair(p,q);
                        p=t.first;
                        q=t.second;
                    }
                    int k;
                    for(k=1;k<=ans&&C[k].second<l;k++);
                    ansl=C[k].first;
                    for(;k<=ans&&C[k].second<=r;k++);
                    ansr=C[k-1].first;
                    if(ansl>ansr)
                        ansl=ansr=1;
                }
            }
        //printf("%d\n",ans);
        printf("%d %d %d\n",ans,ansl,ansr);
    }

    return 0;
}