题目大意:求最长升序子序列
思路:经典DP,虽然简易,但是没有学长上课时的思想的话,估计做的很艰难~~囧。。
状态方程:dp[t] = Max{dp[i] + 1} (a[t] > a[i] && 0 <= i < t)
AC program: #include<iostream> using namespace std; int mm[1005]; int ll[1005]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>mm[i]; } for(int i=0;i<n;i++) { //ll[i]=mm[i]; ll[i]=1; for(int k=0;k<i;k++)/// { if(mm[k]<mm[i] && ll[k]+1>ll[i]) //后面的最长决定于前面的最长,通过扫描自己面前的,选出最长的作为当前ll[I]的值 ll[i]=ll[k]+1; } } int max=ll[0]; for(int i=0;i<n;i++) max=ll[i]>max?ll[i]:max; cout<<max<<endl; system("pause"); return 0;}