洛谷P1091 [NOIP2004 提高组] 合唱队形 |
您所在的位置：网站首页 › 四十人合唱队行 › 洛谷P1091 [NOIP2004 提高组] 合唱队形 |
洛谷P1091 [NOIP2004 提高组] 合唱队形
|
本题是一个简单的 LIS（最长上升子序列）问题 只是要求俩次最长上子序列而已 很容易的 首先由于是最长上升子序列 所以朴素法的动态规划表达式为 f[i] = max( f[i] , f[j] + 1);就是求出到每个点的最长上升子序列而已啦
从题目所给的条件 我们可以推出一下结论 1.本题是要求出从 第一个人到第i个最高的人的最长上升子序列 以及从第i个人到第n个人的最长下降子序列（其实就是第n个人反向到第i个人的最长上升子序列） 2.由于是最长上升子序列 可以想到如下代码 即最长上升子序列的代码 for ( int i = 1; i a[j] ) f[i] = max( f[i] , f[j] + 1); }有了这个代码那我们就可以进一步写出反向的最长子序列的代码 for ( int i = n; i; i-- ) { f[i] = 1; for( int j = n; j > i; j-- ) if( a[i] > a[j] ) f[i] = max(f[i], f[j] + 1); }得到了俩个代码我们就可以写出我们的 Ac Coding #include using namespace std; const int N = 1010; int a[N],f[N],g[N]; int n; int main() { cin >> n; for ( int i = 1; i > a[i]; for ( int i = 1; i a[j] ) f[i] = max( f[i] , f[j] + 1); } for ( int i = n; i; i-- ) { g[i] = 1; for( int j = n; j > i; j-- ) if( a[i] > a[j] ) g[i] = max(g[i], g[j] + 1); } int ans = 0; for ( int i = 1; i |
【本文地址】