USACO白金题目 Subsequence Reversal (range DP / 剪枝 / 记忆化收索)

#include <bits/stdc++.h>

using namespace std;

const int MAX=51;

int d[MAX][MAX][MAX][MAX],a[MAX],n;

int dfs(int l, int r,  int lmx, int rmn){

    if(lmx>rmn){

        return -MAX;

    }

    if(l>r){

        return 0;

    }

    if(d[l][r][lmx][rmn]!=-1){//restore

        return d[l][r][lmx][rmn];

    }

    int res=0;

    res=max(res,dfs(l+1, r,lmx,rmn));//左边不选

    res=max(res,dfs(l, r-1,lmx,rmn));//右边不选

    if(a[l]>=lmx){

        res=max(res,dfs(l+1,r,a[l],rmn)+1);//选左边

    }    

    if(a[r]<=rmn){

        res=max(res,dfs(l,r-1,lmx,a[r])+1);//选右边

    }

    if(a[r]>=lmx && r-l>0){

        res=max(res,dfs(l+1,r-1,a[r],rmn)+1);//交换,选左边,不选右边,不动a数组

    }    

    if(a[l]<=rmn && r-l>0){

        res=max(res,dfs(l+1,r-1,lmx,a[l])+1);//交换,选右边,不选左边,不动a数组

    }

    if(a[l]<=rmn && a[r]>=lmx && r-l>0){//交换,选两边,不动a数组

        res=max(res,dfs(l+1,r-1,a[r],a[l])+2);

    }

    d[l][r][lmx][rmn]=res;//记忆化搜索

    return res;

}    

int main(){

    ifstream fin("subrev.in");

    ofstream fout("subrev.out");

    fin>>n;

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

        fin>>a[i];

    }

    memset(d,-1,sizeof(d));

    fout<<dfs(1,n,0,50);

    return 0;

}