[USACO17JAN] Subsequence Reversal序列反转 (dfs+记忆化)

题目大意：给你一个序列，你可以翻转任意一段子序列一次，求最长不下降子序列长度

tips：子序列可以不连续，但不能破坏在原序列中的顺序

观察数据范围，n<=50，很小，考虑dfs

*dfs来跑区间dp可以巧妙的解决区间两端元素的置换问题

记忆化搜索，f[i][j][l][r] 代表对于区间[i,j]，构成最长不下降子序列的元素值域在[l,r]时，最长不下降子序列的长度

注意特判端点

 #include <bits/stdc++.h>

 #define N 55

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m;

 int a[N],f[N][N][N][N];

 int dfs(int i,int j,int l,int r)

 {

     int ans=-;

     if(f[i][j][l][r]!=-) {return f[i][j][l][r];}

     if(l>r) {return -;}

     if(i>j) {return ;}

     if(i==j&&l<=a[i]&&a[i]<=r) {f[i][j][l][r]=;return ;}

     if(i==j&&(a[i]<l||a[i]>r)) {f[i][j][l][r]=;return ;}

     ans=max(ans,dfs(i+,j,l,r));

     ans=max(ans,dfs(i,j-,l,r));

     ans=max(ans,dfs(i+,j-,l,r));

     if(l<=a[i]&&a[i]<=r) {ans=max(ans,dfs(i+,j,a[i],r)+);}

     if(l<=a[j]&&a[j]<=r) {ans=max(ans,dfs(i,j-,l,a[j])+);}

     if(l<=a[i]&&a[i]<=a[j]&&a[j]<=r) {ans=max(ans,dfs(i+,j-,a[i],a[j])+);}

     if(l<=a[j]) {ans=max(ans,dfs(i+,j-,a[j],r)+);}

     if(a[i]<=r) {ans=max(ans,dfs(i+,j-,l,a[i])+);}

     if(r>=a[i]&&a[i]>=a[j]&&a[j]>=l) {ans=max(ans,dfs(i+,j-,a[j],a[i])+);}

     f[i][j][l][r]=max(,ans);

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

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

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

     memset(f,-,sizeof(f));

     printf("%d",dfs(,n,,));

     return ;

 }

巴特西

[USACO17JAN] Subsequence Reversal序列反转 (dfs+记忆化)

最新文章

热门文章