【模板】线性DP

#include
using namespace std;
const int z = 1024;
int LIS(int *data) {
    int ans = 1, linedp[z];
    memset(linedp,0x7f,(data[0]+1)*sizeof(int));
    linedp[1] = data[1];
    for(int i = 2;i <= data[0];++i) {
    	if(data[i] > linedp[ans])
    		linedp[++ans] = data[i];
    	else 
    		linedp[lower_bound(data+1,data+ans+1,data[i])-data] = data[i];
    }
    return ans;
    //非严格改>为>=，改lower为upper；
    //最少链划分 = 最长反链长度；
}//最长严格上升子序列 
int LCST(char *data,char *datb) {
    int k = 0, linedp[2][z];
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        k = !k;
        for(int j = 0;j < strlen(datb);++j)
            if(data[i] == datb[j])
                linedp[k][j] = linedp[!k][j-1]+1;
            else
                linedp[k][j] = max(linedp[k][j-1],linedp[!k][j]);
    }
    return linedp[k][strlen(datb)-1];
}//最长公共字串； 
int LCSQ(char *data,char *datb) {
    int k = 0, linedp[2][z], len = 0;
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        memset(linedp[!k],0,sizeof(linedp[!k]));
        k = !k;
        for(int j = 0;j < strlen(datb);++j)
            if(data[i] == datb[j]) {
                linedp[k][j] = linedp[!k][j-1]+1;
                len = max(len,linedp[k][j]);
            } 
    }
    return len;
}//最长公共子序列； 
int LCIS(char *data,char *datb) {
    int linedp[z], k = 0;
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        int ans = 0;
        for(int j = 0;j < strlen(datb);++j) {
            if(data[i] > datb[j])
                ans = max(ans,linedp[j]);
            if(data[i] == datb[j])
                linedp[j] = ans+1;
        }
    }
    return linedp[strlen(datb)-1];
}//最长严格上升公共子序列； 
signed main() {
	int data[z];
	for(int i = 0;i <= data[0];++i)
		scanf("%d",&data[i]);
	printf("%d",LIS(data));
    //to do;
}//駄作;