本文主要是介绍洛谷 P3607 [USACO17JAN] Subsequence Reversal P，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源于：洛谷
题目本质：动态规划dp，枚举
题目思路：设一个数组dp[l],[r],[L],[R]，表示从 l 到 r 的区间，值域为 L~R 的最大价值。
状态转移方程为：
dp[l][r][L][R]=max(dp[l][r][L+1][R],dp[l][r][L][R-1]);//把小值域的价值转换到大值域
dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r][L][R]+(a[l]==L));//向左扩展
dp[l][r][L][R]=max(dp[l][r][L][R],dp[l][r-1][L][R]+(a[r]==R));//向右扩展转换后的最长不下降子序列为：
dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r-1][L][R]+(a[l]==R)+(a[r]==L));//序列翻转后，最大价值 ！记得初始化！
完整代码如下：
#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]);
}
这篇关于洛谷 P3607 [USACO17JAN] Subsequence Reversal P的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
