[USACO 2017 Jan P]Subsequence Reversal

Farmer John is arranging his N cows in a line to take a photo (1≤N≤50). The height of the ith cow in sequence is a(i), and Farmer John thinks it would make for an aesthetically pleasing photo if the cow lineup has a large increasing subsequence of cows by height.

To recall, a subsequence is a subset of elements from the cow sequence, found at some series of indices . We say the subsequence is increasing if .

FJ would like there to be a long increasing subsequence within his ordering of the cows. In order to ensure this, he allows himself initially to choose any subsequence and reverse its elements.

For example, if we had the list

1 6 2 3 4 3 5 3 4

We can reverse the chosen elements

1 6 2 3 4 3 5 3 4   ^         ^ ^ ^

to get

1 4 2 3 4 3 3 5 6   ^         ^ ^ ^

Observe how the subsequence being reversed ends up using the same indices as it initially occupied, leaving the other elements unchanged.

Please find the maximum possible length of an increasing subsequence, given that you can choose to reverse an arbitrary subsequence once.

#include<bits/stdc++.h> using namespace std; const int N=52; int a[N],f[N][N][N][N]; void chmax(int &x,int y) { if(x<y)x=y; } int main() { int n,i,l,r,down,up; scanf("%d",&n); for(i=1;i<=n;++i) {scanf("%d",a+i); for(down=1;down<=a[i];++down) for(up=a[i];up<=50;++up) f[i][i][down][up]=1; } for(int l1=2;l1<=n;++l1) for(l=1,r=l1;r<=n;++l,++r) for(int l2=1;l2<=50;++l2) for(down=1,up=l2;up<=50;++down,++up) { int ans=max(f[l][r][down+1][up],f[l][r][down][up-1]); chmax(ans,f[l+1][r][down][up]+(down==a[l])); chmax(ans,f[l][r-1][down][up]+(up==a[r])); chmax(ans,f[l+1][r-1][down][up]+(down==a[r])+(up==a[l])); f[l][r][down][up]=ans; } printf("%d\n",f[1][n][1][50]); }

详情