題意
給定一個數組
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=,MAXL=;
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=;i<=N;i++)
scanf("%1d",&A[i]);
int ans=,ansl,ansr;
for(int x=;x<;x++)
for(int y=x;y<;y++)
{
M=;
int l,r;
for(int i=;i<=x;i++)
B[++M]=i;
l=M+;
for(int i=y;i>=x;i--)
B[++M]=i;
r=M;
for(int i=y;i<;i++)
B[++M]=i;
for(int i=;i<=N;i++)
for(int j=;j<=M;j++)
{
if(dp[i][j-]<dp[i-][j]+(A[i]==B[j]))
{
dp[i][j]=dp[i-][j]+(A[i]==B[j]);
path[i][j]=make_pair(i-,j);
}
else
{
dp[i][j]=dp[i][j-];
path[i][j]=make_pair(i,j-);
}
}
if(dp[N][M]>ans)
{
ans=dp[N][M];
int p=N,q=M,top=ans;
ansl=-,ansr=-;
pair<int,int> t;
while(p&&q)
{
t=path[p][q];
if(dp[t.first][t.second]+==dp[p][q]&&A[p]==B[q])
C[top--]=make_pair(p,q);
p=t.first;
q=t.second;
}
int k;
for(k=;k<=ans&&C[k].second<l;k++);
ansl=C[k].first;
for(;k<=ans&&C[k].second<=r;k++);
ansr=C[k-].first;
if(ansl>ansr)
ansl=ansr=;
}
}
//printf("%d\n",ans);
printf("%d %d %d\n",ans,ansl,ansr);
}
return ;
}