一、最长上升子序列（LIS）
题意
给定n个整数A1,A2…An,从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变。）例如序列1,6,2,3,7,5，可以选出上升子序列·1,2,3,5，也可以选出1,6,7，但前者跟车，选出的上升子序列中相邻的元素不能相等。（紫书P274）
O（n^2）作法分析
用dp保存以位置i结尾的最长上升序列的长度，后继dp从其中寻找满足条件的最大值即可。
#include <stdio.h>
#include <stdlib.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 1000
int main()
{
int dp[N]={0}; //表示以第几个数结尾的最长子序列数
int n;
scanf("%d",&n);
int *num;
num=(int *)calloc(n,sizeof(int)); //初始化为0
int i,j;
for(i=0;i<n;i++)
scanf("%d",&num[i]);
dp[0]=1;
for(i=0;i<n;i++)
for(j=0;j<i;j++)
if(num[i]>num[j])
dp[i]=Max(dp[i],dp[j]+1);
//此步可以和上方i循坏一起进行
int ans=0;
for(i=0;i<n;i++)
if(dp[i]>ans)
ans=dp[i];
printf("%d",ans);
return 0;
}
二、最长公共子序列（LCS）
题目描述
给出 1,2,…n 1,2,…,n 的两个排列 ，求它们的最长公共子序列。
输入格式
第一行是一个数 nn。
接下来两行，每行为 nn 个数，为自然数 1,2,\ldots,n1,2,…,n 的一个排列。
输出格式
一个数，即最长公共子序列的长度。
输入输出样例
输入
5
3 2 1 4 5
1 2 3 4 5
输出
3
分析
O（n^2）的作法
状态转移方程dp（i，j），i代表A的结尾，j代表B的结尾
①Ai==Bj：dp(i,j)=dp(i-1,j-1)+1
②Ai!=Bj：dp（i,j）=Max(dp(i-1,j),dp(i,j-1))
#include <stdio.h>
#include <stdlib.h>
#define Max(a,b) ((a)>(b)?(a):(b))
//用dp[i][j]表示A[i]与B[j]的最长公共子序列
int main()
{
int i,j;
int **dp;
int *A,*B;
int n;
scanf("%d",&n);
A=(int *)calloc(n+1,sizeof(int));
B=(int *)calloc(n+1,sizeof(int));
dp=(int **)calloc(n+1,sizeof(int *));
for(i=0;i<n+1;i++)
dp[i]=(int *)calloc(n+1,sizeof(int));
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
for(i=1;i<=n;i++)
scanf("%d",&B[i]);
//初始化遇到相同的后面的i才会为1
for(i=1;i<=n;i++)
if(A[1]==B[i])
dp[1][i]=1;
else
dp[1][i]=dp[1][i-1];
for(i=1;i<=n;i++)
if(A[i]==B[1])
dp[i][1]=1;
else
dp[i][1]=dp[i-1][1];
int max=0;
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(A[i]==B[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=Max(dp[i-1][j],dp[i][j-1]);
if(dp[i][j]>max)
max=dp[i][j];
}
}
printf("%d",max);
return 0;
}
三、照明系统设计（LIS升级）
题目描述
设计一个照明系统。共有n种灯泡供你选择，不同种类的灯泡必须使用不同种类的电源，但同一种灯泡可以共用一个电源。所有灯泡的电流参数相同，电压不同。现在给你每种灯泡的四个参数：电压V，电源费用K,每个灯泡的价格C，以及需要该种灯泡的数量L。为了减少费用，你可以把电压低的灯泡换成电压更高的灯泡，而省出电源的费用（某种灯泡全换成别的种类，就可以共用别的电源，从而少配一个电源，不就节约了一个电源的费用吗？）。请你配置方案，使系统造价最小。新的方案标准不能降低，灯泡的数量不能减少，电流相同、电压高的灯泡功率也更大，也会更亮。
输入格式
第一行包括一个正整数n，接下来的n行，每行描述一种灯泡的参数，分别为V，K，C和L。两数之间用一个空格分隔。
输出格式
一个数表示电源的最小费用。
输入样例
3
12 300 10 30
18 400 15 28
30 500 13 30
3
3 100 500 10
20 120 600 8
16 220 400 7 18
输出样例
1644
778
分析
假设要以灯泡i换前面的第j种灯泡，如果能够节省经费的话就意味着灯泡i单价（C）小于灯泡j单价，或者说节省下来的电费加灯泡总价更小，这两种情况都好，我们要换灯泡就要换该种的所有灯泡，才最省钱，不然要付两种电费不是很亏？
先把灯泡按照电压从小到大排序，设s【i】为前i种灯泡的总数。
状态转移方程：dp（i）=Min（dp（j）+（s【i】-s【j】）*c【i】+k【i】）
再往细里去讨论：为什么以此确立状态转移方程？假设i(i>j)的前方j（j>3），第一种灯泡很便宜我们不换，状态转移方程会保存下来，第2和3种灯泡中3更优惠我们会全换，故到了dp【4】我们状态转移方程里就会有s【4】-s【2】和s【4】-s【3】进行比较。
#include <stdio.h>
#include <stdlib.h>
#define N 102
#define Min(a,b) ((a)<(b)?(a):(b))
typedef struct
{
int v;
int k;
int c;
int l;
} Lamp;
void q_sort(Lamp a[],int start,int end)
{
if(start>end)
return ;
int i=start;
int j=end;
Lamp t=a[start];
while(i<j)
{
while(i<j && a[j].v>=t.v)
j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j && a[i].v<=t.v)
i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=t;
q_sort(a,start,i-1);
q_sort(a,i+1,end);
}
int main()
{
Lamp la[N];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d%d%d",&la[i].v,&la[i].k,&la[i].c,&la[i].l);
q_sort(la,0,n-1);
int dp[N];
dp[0]=la[0].k+la[0].c*la[0].l;
int s[N]={0};
s[0]=la[0].l;
for(int i=1;i<n;i++)
s[i]=s[i-1]+la[i].l;
for(int i=1;i<n;i++){
dp[i]=s[i]*la[i].c+la[i].k; //全部换成该种灯泡
for(int j=0;j<i;j++)
{
dp[i]=Min(dp[i],dp[j]+(s[i]-s[j])*la[i].c+la[i].k);
}
}
printf("%d",dp[n-1]);
return 0;
}