动态规划
去年选拔赛的一个题目，题意就是给一个序列，要找出一个子序列，一增一减（第偶数个元素要比它前面的元素小，第奇数个元素要比它前面的元素大）
算是比较基础的DP，属于"第i个元素与它前面i-1的元素形成的一种关系，最后变为前i个元素的信息"
dp[i]表示加入第i个数字，与前i-1个数字能形成的最大长度，因此面对两个两个问题，第i个元素会不会加入到最终的最长子序列中，要加的话怎么加
先看方程 dp[i]=max{ dp[j] } + 1;
若dp[j]为奇数，若想加入第i个元素，那么第i个元素将会是子序列中的第偶数个元素，那么还要满足a[i]<a[j]
若dp[j]为偶数，若想加入第i个元素，那么第i个元素将会是子序列中的第奇数个元素，那么还要满足a[i]>a[j]
因而要从1到i-1扫一次，以便找到符合要求的而且最大的dp[j]去更新dp[i]
在更新前应先初始化dp[i]=1; 表示第i个元素本身就能形成一个子序列
更新完后，若dp[i]=1，那么说明其实找不到一个符合条件的dp[j]，这其实回答了我们的第一个问题 “第i个元素会不会加入到最终的最长子序列中”
最终最长的子序列，无非就是扫一次整个dp数组，找到最大值，就是我们要的答案
这种基础的DP往往付出的时间复杂度就是O(n*n)，因为第i个元素与它前面所有的元素都有关系，需要一一判断
#include <cstdio> #include <cstring> #define N 1010 #define INF 0x3f3f3f3f #define max(a,b) a>b?a:b int a[N],dp[N],n,ans; int main() { while(scanf("%d",&n)!=EOF && n) { for(int i=1; i<=n; i++) scanf("%d",&a[i]); dp[1]=1; if(a[2]<a[1]) dp[2]=2; else dp[2]=1; ans=1; for(int i=3; i<=n; i++) { dp[i]=1; //初始化 for(int j=i-1; j>0; j--) if( dp[j]&1 && a[i]<a[j]) //前j个数字中已经选出了奇数个 dp[i]=max(dp[i] , dp[j]+1); else if( !(dp[j]&1) && a[i]>a[j]) //前j个数字中已经选出了偶数个 dp[i]=max(dp[i] , dp[j]+1); ans=max(ans,dp[i]); } printf("%d\n",ans); } return 0; }