动态规划

求最长上升/下降子序列

for(int i=1; i<=n; i++){
	f[i] = 1;
    for(int j=1; j<i; j++){
    	if(a[j] < a[i])f[i] = max(f[i], f[j]+1);
	}
}//求最长上升子序列

for(int i=n; i>=1; i--){
	g[i] = 1;
	for(int j=i+1; j<=n; j++){
		if(a[i] > a[j])g[i] = max(g[i], g[j]+1);
	} 
}//求最长下降子序列 

求离散化

//离散化 
int a[100005];
vector<int> v;
for(int i=1; i<=n; i++){
	v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
//unique():1 2 2 3 -> 1 2 3 2
for(int i=1; i<=n; i++)a[i] = lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;

滚动数组

//滚动数组 
int v[MAXN],w[MAXN],f[2][MAXN],now;
memset(f,~0x3f,sizeof(f));
now=0;
f[now][0] = 0;
for(int i = 1; i <= n; i++){
    //i-1行数组f[now],第i行的数组对应f[now^1] 
    memset(f[now^1], ~0x3f, sizeof(f[now^1]));
    for(int j = 0; j <= m; j++){
    	f[now^1][j] = f[now][j];
    	if(j >= w[i])f[now^1][j] = max(f[now^1][j],f[now][j-w[i]]+v[i])
	}
	now ^= 1;
}

树形DP

P1352 没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
int n,r[6005],l,k,ans,f[6005][2];
vector<int> G[6005];
void dfs(int v,int fa=0){
    f[v][0]=0;//该职员不来
    f[v][1]=r[v];//来
    for(int i=0;i<G[v].size();i++){
        int x=G[v][i];//职员x
        if(x==fa)continue;//避免访问到父亲
        dfs(x,v);//先计算子树x的dp值，保存到f[x][0/1]
        f[v][0]+=max(f[x][0],f[x][1]);//如果不来，快乐指数取两个儿子中最大的
        f[v][1]+=f[x][0];//如果v来，那么x不能来
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&r[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&l,&k);
        G[l].push_back(k);
        G[k].push_back(l);//添加l和k是直接的上司和下属
    }
    dfs(1);
    ans=max(f[1][0],f[1][1]);//答案取两种方案中快乐指数最大的
    printf("%d\n",ans);
    system("pause");//防止运行后自动退出，需头文件stdlib.h
    return 0;
}//P1352