http://poj.org/problem?id=2533
题意：给你n（1-1000）个数，求这n个数的最长升序列。
题解：dp【i】表示以第i个数结尾的最长升序列。
#include <iostream>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
int v[] , w[] , dp[] , a[]; int main()
{
int n ;
while(cin >> n)
{
for(int i = ; i <= n ; i++)
{
cin >> a[i] ;
dp[i] = ;
}
for(int i = ; i <= n ; i++)
{
for(int j = ; j < i ; j++)
{
//dp[i]记录以i结尾的前i个最长上升子序列
if(a[j] < a[i]) // dp[j] 代表前j个子序列的最长上升子序列
{
dp[i] = max(dp[i] , dp[j] + ); // 如果第i个数大于第j个数，就在前j个最长子序列的个数上加一再比较
}
}
}
int max1 = ; // 注意不要认为dp[n]就是整个序列的最大子序列。他只是n为结尾的最大子序列
for(int i = ; i <= n ; i++)//例如 ： 1 2 3 100 1 .这里的dp[n] = 1 ;
{
if(max1 < dp[i])
max1 = dp[i] ;
}
cout << max1 << endl ; } return ;
}
优化：另开一个数组dp该数组长度始终是进行到某点的最长长度，且该数组是递增的，但不一定是该序列的最长上升序列，例如：3 5 1 ，该数组为1 5。
该数组有两种操作：1、如果a【i】大于dp的最后一个元素，则直接加到dp数组末尾。
2、如果小于等于，对dp数组中的元素进行二分查找找到大于a[i]的下标，并将其替换。
note：lower_bound找到第一个大于等于a[i]的下标，upper_bound找到第一个大于a[i]的下标。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int a[];
int dp[]; int main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:/c++/in.txt", "r", stdin);
freopen("D:/c++/out.txt", "w", stdout);
#endif*/
int n ;
scanf("%d" , &n);
for(int i = ; i <= n ; i++)
{
scanf("%d" , &a[i]);
}
int l = ;
dp[l++] = a[];
for(int i = ; i <= n ; i++)
{
if(a[i] > dp[l-])
{
dp[l++] = a[i];
}
else{
int index = lower_bound(dp , dp+l , a[i]) - dp;//upper_bound找到第一个大于a【i】的下标，一样ac
dp[index] = a[i];
}
}
cout << l << endl ; return ;
}
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int a[];
int dp[]; int halfsearch(int *a , int len , int x)//upper_bound实现
{
int l = , r = len , mid = (l+r) >> ;
while(r >= l)
{
if(a[mid] > x)//目标在左边
{
r = mid - ;
}
if(a[mid] <= x)//不取等就TLE.
{
l = mid + ;
}
mid = (l + r) >> ;
}
return l ;
} int main()
{
/*#ifdef ONLINE_JUDGE
#else
freopen("D:/c++/in.txt", "r", stdin);
freopen("D:/c++/out.txt", "w", stdout);
#endif*/
int n ;
scanf("%d" , &n);
for(int i = ; i <= n ; i++)
{
scanf("%d" , &a[i]);
}
int l = ;
dp[l] = a[];
for(int i = ; i <= n ; i++)
{
if(a[i] > dp[l])
{
dp[++l] = a[i];
}
else{
int index = halfsearch(dp , l , a[i]);
dp[index] = a[i];
}
for(int i = ; i <= l ; i++)
{
cout << dp[i] << " ";
}
cout << endl ;
}
cout << l << endl ; return ;
}
题意：给你n个数，求一个序列的和最大，条件是该序列是递增的。
题解：跟最长子序列很像但有区别，区别就是最长子序列的和不一定是最大的。比如：1 100 2 3 4 . 最长子序列和为10 ， 而答案应该是101.
该题求的是递增序列的最大和。不一定是最长。
#include <iostream>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
int v[] , w[] , dp[] , a[] ;
int len1 , len2 ; int main()
{
int n ;
while(~scanf("%d" , &n) && n )
{
for(int i = ; i <= n ; i++)
{
scanf("%d" , &a[i]);
dp[i] = a[i] ;
}
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= i ; j++)
{
if(a[i] > a[j])
{
dp[i] = max(dp[i] , dp[j] + a[i]);//d[i]以i结尾的最大子序列和
}
}
}
int max1 = ;
for(int i = ; i <= n ; i++)
{
if(max1 < dp[i])
max1 = dp[i] ;
}
cout << max1 << endl ; } return ;
}