【[USACO17JAN]Subsequence Reversal P】题解

· · 题解

前言

希望审核能给我过了这篇题解 。

题目

题目传送门

正文

很巧妙的思维题啊 ， 一开始丝毫没有思路 ， 瞟了一眼题解 ， 看到一句话 ： 交换一个序列相当于不相交的交换几个元素 ， 因为这几个元素交换之后就相当于是交换了一个子序列 。

有了这句话的提示 ， 问题就迎刃而解了 ， 关键要做到交换的元素不能相交 ， 其实只需要 DP 的顺序没问题即可 ， 那么显然假设 [L,R] 已经解决了 ， 那么交换的元素就强制只能在 [L,R] 之外 。 下面正式开始 DP ， 定义 dp_{l,r,i,j} 表示区间 [l,r] 间 ， 值域在 [i,j] 间的最长上升子序列的长度 ， 那么就转移就是交换和不交换的区别 。

不交换的转移 :

dp_{l,r,i,j}=\max(dp_{l+1,r,i,j}+(a_{l}==i),dp_{l,r-1,i,j}+(a_{r} == j))

交换的转移 :

dp_{l,r,i,j}=\max(dp_{l,r,i,j},dp_{l+1,r-1,i,j}+(a_{l}==j)+(a_{r} == i))

注意值域是可以向两边扩展的 。

AC code :

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int read() {
    int s = 0, f = 1;
    char a = getchar();
    while(a < '0' || a > '9') {
        if(a == '-') f = -1;
        a = getchar();
    }
    while(a <= '9' && a >= '0') s = s * 10 + a - '0', a = getchar();
    return s * f;
}
LL dp[55][55][55][55],n,m,a[55],p;
int main() {
    n=read();
    for(int i=1; i<=n; i++) {
        a[i]=read();
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=a[i];j++) {
            for(int k=a[i];k<=50;k++) {
                dp[i][i][j][k]=1;
            }
        }
    }
    for(int len=2;len<=n;len++) {
        for(int l=1;l<=n;l++) {
            int r=l+len-1; if(r>n) break;
            for(int i=1;i<=50;i++) {
                for(int j=i;j<=50;j++) {
                    dp[l][r][i][j]=max(dp[l][r][i][j],max(dp[l+1][r][i][j]+(a[l]==i),dp[l][r-1][i][j]+(a[r]==j)));
                    dp[l][r][i][j]=max(dp[l][r][i][j],dp[l+1][r-1][i][j]+(a[r]==i)+(a[l]==j));
                    dp[l][r][i][j+1]=max(dp[l][r][i][j+1],dp[l][r][i][j]);
                    dp[l][r][i-1][j]=max(dp[l][r][i-1][j],dp[l][r][i][j]);
                }
            }
            for(int i=1;i<=50;i++) {
                for(int j=i;j>=1;j--) {
                    dp[l][r][j-1][i]=max(dp[l][r][j-1][i],dp[l][r][j][i]);
                }
            }
        }
    }
    printf("%lld",dp[1][n][1][50]);
}

最后希望这篇题解能帮到屏幕前的你 ， 但是不要抄袭哦 ！