HDU-1087.SuperJUmpingJUmpingJumping.(DP and LISPP)

　　本题大意：给定一个长度为n的序列a，让你输出这个序列子序列中元素和最大的最大上升子序列。

　　本题思路：一开始肯定可以想到用LIS实现，我们用LIS实现的时候可以发现这个问题并不满足LIS问题的最优子结构，即两者的子问题肯定是不相同的...比如5 2 2 2 1 2 3，在这五个数中，如果按照LIS你会发现dp[3] = 2 ，dp[ 4] = 2，那么dp[5]呢，dp[5] = 3，刚好是不满足LIS求解的性质的，也就是违反了LIS的最优子结构性质，那么我们要如何才能得到另一份最优子结构呢，我看可以看到dp[4] = dp[3] + a[4] ，那么也就是如果我们assume dp[ i ] instead of 以i结尾的最大上升子序列，那么就可以得到一个状态转移方程dp[ i ] = max(dp[ j ] + a[ i ], dp[ i ])(j < i)，接下来看代码......

　　千万不要认为局部LIS和整体LIS的思路相同，否则你会陷入一个僵局......

　　参考代码：

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, a[maxn], dp[maxn];

 int main () {

     while(cin >> n && n) {

         memset(dp, , sizeof dp);

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

             cin >> a[i];

         dp[] = a[];

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

             dp[i] = a[i];

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

                 if(a[i] > a[j])

                     dp[i] = max(dp[j] + a[i], dp[i]);

         }

         cout << *max_element(dp, dp + maxn) << endl;

     }

     return ;

 }

巴特西

HDU-1087.SuperJUmpingJUmpingJumping.(DP and LISPP)

最新文章

热门文章