Espylacopa dp专题训练

noip Dynamic Programming

 A - Jury Compromise POJ 1015

题意：

有n(<=200)个人作为陪审团的被选举成员,分别有正方和反方给予的评价,要求在这n个人中选出m(<=20)个人,在保证正方评价之和与反方评价之和差最小的情况下,使得评价分数总和最高。

题解：

0.定义状态fi][k]当前已经选取了i个人并且这i个人的差值为k时的评分总和的最大值,p[i][k]当前已经选取了i个人并且这i个人的差值为k时第i个人的编号。

1.如果令c[i]表示第i个人正方与反方的差,s[i]表示第i个人正方与反方的和,那么状态转移f[i][k+c[j]] = f[i-1][k]+s[j],p[i][k+c[j]] = j 条件:f[i][k+c[j]] < f[i-1][c[j]]+s[j]&&当前选的这第i个人(j)没有被选过.边界为dp[0][0] = 0;

2.但是下标的差值有可能为负数,那么下标总体往右平移就好了,最后再找出差值最小的dp状态,那么正方的总和为(dp[m][c]+c)/2,反方即为(dp[m][c]-c)/2

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e3+7;
int kase = 0,n,m,c[N],a[N],b[N],s[N],d[N][N],p[N][N],ret[N];

bool select(int i,int k,int x,int c[]){
	while(i && p[i][k] != x)k -= c[p[i][k]],--i;
	return i;
}

void print(int i,int k,int c[]){
	while(i)ret[i] = p[i][k],k -= c[p[i][k]],--i;
	sort(ret+1,ret+1+m);
	for(int i = 1;i <= m;++i)printf("%d ",ret[i]);
	cout<<endl<<endl;
}

int main(){
	while(scanf("%d%d",&n,&m) != EOF && n && m){
		memset(d,-1,sizeof(d));
		memset(p,-1,sizeof(p));
		for(int i = 1;i <= n;++i){
			scanf("%d%d",&a[i],&b[i]);
			c[i] = a[i]-b[i],s[i] = a[i]+b[i];
		}
		int M = 20*m;
		d[0][M] = 0;
		for(int i = 1;i <= m;++i){
			for(int k = 0;k <= 2*M;++k)if(d[i-1][k]>=0){
				for(int j = 1;j <= n;++j)if(d[i][k+c[j]]<d[i-1][k]+s[j] && !select(i-1,k,j,c)){
					p[i][k+c[j]] = j;
					d[i][k+c[j]] = d[i-1][k]+s[j];
				}
			}
		}
		int x;
		for(x = 0;x <= M;++x)if(d[m][M-x] >= 0 || d[m][M+x] >= 0)break;
		int minc = d[m][M-x]>d[m][M+x]?M-x:M+x;
		printf("Jury #%d
",++kase);
		printf("Best jury has value %d for prosecution and value %d for defence:
",(d[m][minc]+minc-M)>>1,(d[m][minc]-minc+M)>>1);
		print(m,minc,c);
	}
}

　　

B - Number Game POJ 1143

题意：

给出n(<=20)个数字,有两个玩家在玩关于这串数字的游戏,一个人开始取数,假如取走一个数字为a并且当前b是被选过,那么所有的数字为a*k0+b*k1的数字都不能选,询问第一个玩家的必胜点。

题解：

0.数据范围太小,考虑状态压缩,定义dp[S]表示当前状态是否为必胜点.

1.令状态S表示某个数是否被选,如果S这个状态是必胜点,那么S的后继S'必定为必败点,状态转移dp[S] = dp[S']^1.边界为dp[(1<<21)-1] = 0,全选时必败

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2e1+7;
const int AS = (1<<21)-1;
int dp[AS<<1],S,n,kase,ret[N],cnt,x[N];

int update(int S,int x){
	S |= 1<<x;
	for(int i = 2;i+x <= 20;++i)if(S&(1<<i))S |= 1<<i+x;
	return S;
}

int search(int S){
	if(dp[S] != -1)return dp[S];
	for(int i = 2;i <= 20;++i)if(!(S&(1<<i))){
		int S0 = update(S,i);
		if(!search(S0))return dp[S] = 1;
	}
	return dp[S] = 0;
}

int main(){
	while(scanf("%d",&n) && n){
		memset(dp,-1,sizeof(dp));
		S = AS,dp[AS] = 0,cnt = 0;
		for(int i = 0;i < n;++i)scanf("%d",&x[i]),S ^= 1<<x[i];
		for(int i = 0;i < n;++i){
			int S0 = update(S,x[i]);
			if(!search(S0))ret[++cnt] = x[i];
		}
		printf("Test Case #%d
",++kase);
		cnt ? printf("The winning moves are:") : printf("There's no winning move.");
		for(int i = 1;i <= cnt;++i)printf(" %d",ret[i]);
		cout<<endl<<endl;
	}
	return 0;
}

　　

C - Prison rearrangement POJ 1636

题意：

有A,B两个监狱里面都有有n(<=200)个罪犯,现在需要将A监狱的罪犯和B监狱的罪犯进行交换,最多交换n/2个人,但是AB两监狱囚犯有的存在仇恨关系,所以要避免这两个囚犯在同一个监狱。

题解：

0.如果从A监狱选出一个罪犯a并且与B监狱的罪犯b有仇恨,但是b与A监狱的c有仇恨......所以一次调动要把a,c,e...与b,d,f...进行交换,那么就可以把所有一次性关联仇恨的人都处理出来,S0[T]表示A监狱第T个仇恨集合的人数,S1[T]则表示B监狱。

1.定义状态dp[i][j]表示在A监狱交换i个人B监狱交换j个人是否可行.

2.状态转移dp[i][j] = dp[i-S0[k]][j-S0[k]] || dp[i][j].

3.最后输出下标值最大的并且dp值为1的下标.

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 420;
const int M = 40010;
#define clr(a,b) memset(a,b,sizeof(a))

int n,m,kase;

int head[N],ecnt;
struct edge{int v,nxt;}e[M<<1];
void adde(int u,int v){e[ecnt] = (edge){v,head[u]};head[u] = ecnt++;}

int vis[N],T;

int dp[N][N],S0[N],S1[N];

void pre(){
	T = 0,clr(vis,0),clr(S0,0),clr(S1,0);
	ecnt = 0,clr(head,-1),clr(e,0),clr(dp,0);
}

void dfs(int u){
	vis[u] = 1;
	u <= n ? S0[T] += 1 : S1[T] += 1;
	for(int it = head[u];it != -1;it = e[it].nxt)if(!vis[e[it].v])dfs(e[it].v);
}

int main(){
	scanf("%d",&kase);
	while(kase--){
		pre();
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= m;++i){
			int u,v;
			scanf("%d%d",&u,&v);v += n;
			adde(u,v),adde(v,u);
		}
		for(int i = 1;i <= n<<1;++i)if(!vis[i])++T,dfs(i);
		dp[0][0] = 1;
		for(int k = 1;k <= T;++k){
			for(int i = n>>1;i >= S0[k];--i){
				for(int j = n>>1;j >= S1[k];--j){
					dp[i][j] = dp[i][j] || dp[i-S0[k]][j-S1[k]];
				}
			}
		}
		for(int i = n>>1;i >= 0;--i)if(dp[i][i]){
			printf("%d
",i);break;
		}
	}
	return 0;
}

　　

D - Clans on the Three Gorges POJ 1682

题意：

有三个河岸分别有N,M,K个部落,不在同一个河岸的部落都可以是友好的,现在需要加强沟通在两个部落之间修桥,使得任意一个部落都至少有一座桥,但是每个部落都有一个海拔,所以桥的花费是两个部落之间的海拔高度差的绝对值,求最小的花费。

题解：

0.定义dpN[i][j]表示:i j修一座桥并且i~n与1~j联通,dpM[j][k]表示:j k修一座桥并且j~M联通1~k,dpK[k][i]表示:k i修一座桥并且k~n到1~i的最小费用。

1.状态转移：dp[i][j] = min{dp[i+1][j],dp[i+1][j-1],dp[i][j-1]+abs(H[i]-H[j])}

2.dp的整合方式有以下八种

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 110;
const int inf = 1e8;

int n,m,k,A[N],B[N],C[N],kase;
int dN[N][N],dM[N][N],dK[N][N];

#define mini(a,b,c) min(min(a,b),c)
int main(){
	scanf("%d",&kase);
	while(kase--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i = 1;i <= n;++i)scanf("%d",&A[i]);
		for(int i = 1;i <= m;++i)scanf("%d",&B[i]);
		for(int i = 1;i <= k;++i)scanf("%d",&C[i]);
		for(int i = 0;i < N;++i)
			for(int j = 0;j < N;++j)
				dN[i][j] = dM[i][j] = dK[i][j] = inf;

		dN[n+1][0] = dM[m+1][0] = dK[k+1][0] = 0;
		for(int i = n;i >= 1;--i)
			for(int j = 1;j <= m;++j)
				dN[i][j] = mini(dN[i+1][j-1],dN[i+1][j],dN[i][j-1])+fabs(A[i]-B[j]);

		for(int i = m;i >= 1;--i)
			for(int j = 1;j <= k;++j)
				dM[i][j] = mini(dM[i+1][j-1],dM[i+1][j],dM[i][j-1])+fabs(B[i]-C[j]);

		for(int i = k;i >= 1;--i)
			for(int j = 1;j <= n;++j)
				dK[i][j] = mini(dK[i+1][j-1],dK[i+1][j],dK[i][j-1])+fabs(C[i]-A[j]);
				
		int ret = inf;
		for(int i = 0;i <= n+1;++i)
			for(int j = 0;j <= m+1;++j)
				for(int l = 0;l <= k+1;++l){
					ret = min(ret,dN[i][j]+dM[j][l]+dK[l][i]);
					
					ret = min(ret,dN[i+1][j]+dM[j][l]+dK[l][i]);
					ret = min(ret,dN[i][j]+dM[j+1][l]+dK[l][i]);
					ret = min(ret,dN[i][j]+dM[j][l]+dK[l+1][i]);
					
					ret = min(ret,dN[i+1][j]+dM[j+1][l]+dK[l][i]);
					ret = min(ret,dN[i][j]+dM[j+1][l]+dK[l+1][i]);
					ret = min(ret,dN[i+1][j]+dM[j][l]+dK[l+1][i]);
					
					ret = min(ret,dN[i+1][j]+dM[j+1][l]+dK[l+1][i]);
				}
	
		cout<<ret<<endl;
	}
	return 0;
}

　　

E - Crossed Matchings POJ 1692

题意：

给出两个长度为N(<=1000)的数列A,B,求最大的匹配数,匹配规则为对于一个数i,另外一个数列中有一个数与她相等并且有且只有一个匹配与之交叉,(每个数只能匹配一次)。

题解：

0.定义状态：dp[i][j]表示考虑A数列中前i个数和B数列前j个数的最大匹配数。

1.状态转移：

①dp[i][j] = max{dp[i-1][j],dp[i][j-1]}不匹配当前的A[i]或B[j]

②dp[i][j] = max{dp[S0-1][S1-1]+2}(A[i] != B[j] && A[S0] == B[j] && A[i] == B[S1])

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e3+7;
int kase,n,m,dp[N][N],A[N],B[N];

int main(){
	scanf("%d",&kase);
	while(kase--){
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= n;++i)scanf("%d",&A[i]);
		for(int i = 1;i <= m;++i)scanf("%d",&B[i]);
		memset(dp,0,sizeof(dp));
		for(int i = 2;i <= n;++i){
			for(int j = 2;j <= m;++j){
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				if(A[i] == B[j])continue;
				int S0 = 0,S1 = 0;
				for(S0 = i-1;S0 >= 1;--S0)if(A[S0] == B[j])break;
				for(S1 = j-1;S1 >= 1;--S1)if(A[i] == B[S1])break;
				if(S0&&S1)dp[i][j] = max(dp[i][j],dp[S0-1][S1-1]+2);
			}
		}
		cout<<dp[n][m]<<endl;
	}
	return 0;
}

　　

F - SUBTRACT POJ 1722

题意：

定义一种操作,操作con{i}就是将a[i]-a[i+1]取出进行合并,再加入到a[i]的位置，a[i+1]消失,进行n-1次操作后,会剩下一个数字.给定长度为n(<=100)的数列及目标t（最后剩下的数字）,求操作顺序(Special Judge).

 

题解：

0.问题的实质就是在数列中添加'+'或者'-'使得答案等于目标t

1.

①把所有括号拆掉，结果的式子一定一这样的：a[1]-a[2]±a[3]±a[4]±...±a[n] = 目标数

②移项±a[3]±a[4]±...±a[n] = 目标数-a[1]+a[2].

③2*a[3]  2*a[4]  2*a[5] ... 2*a[n]  = 目标数-a[1]+a[2] + (a[3]+a[4]+a[5]+...+a[n])

④如果某一个数取了便是正号,不取便是负号,对于一个数取还是不取是一个很显然背包Dp

2.从左往右扫过来，如果数a[i]的符号为正，则让它与左边的数合并。最后，所有的数都和1合并。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e2+7;
const int M = 1e4+7;
#define clr(a,b) memset(a,b,sizeof(a))
int n,t,d[M],p[N][M],flag[N],ret[N],x[N];

int main(){
	while(scanf("%d%d",&n,&t) != EOF){
		int sum = 0,cnt = 0;
		clr(d,0),clr(flag,0),clr(p,0);
		for(int i = 1;i <= n;++i)scanf("%d",&x[i]),sum += x[i],x[i]<<=1;
		t = t+sum-x[1];
		for(int i = 3;i <= n;++i){
			for(int j = t;j >= x[i];--j){
				if(d[j] > d[j-x[i]]+x[i])p[i][j] = 0;
				else d[j]=d[j-x[i]]+x[i],p[i][j] = 1;
			}
		}
		int v = t;
		for(int i = n;i >= 3;--i)if(p[i][v])flag[i] = 1,v -= x[i];
		for(int i = 3;i <= n;++i)if(flag[i])ret[++cnt] = i-1;
		for(int i = 0;i < cnt;++i)ret[i+1] -= i;
		for(int i = 1;i <= cnt;++i)printf("%d
",ret[i]);
		for(int i = cnt+1;i < n;++i)puts("1");
	}
	return 0;
}

　　

G - Special Experiment POJ 1770

题意：

有n(<=200)个原子和m(<=200)个光子，选出最大能量的原子集合,但是如果有任意两个原子的能力差等于一个光子的能量,那么这种方案是不行的。

题解：

0.如果两个原子的能量的差等于一个光子的能量,那么他们就面对选或是不选的情况,题目需要求最大能量的原子集合,那么是明显的树形dp(类似于"没有上司的舞会")

1.定义状态：dp[u][0/1]表示不选/选u这个节点的最大能量

2.状态转移：dp[u][0] += {max(dp[v][0],dp[v][1])}

　　　　　　dp[u][1] += {dp[v][0]}+w[u]

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e3+47;
int n,m,x,w[N],flag[1000000],ecnt,head[N],vis[N],dp[N][2];
struct edge{int v,nxt;}e[N*N];
#define clr(a,b) memset(a,b,sizeof(a))
void adde(int u,int v){e[ecnt].v = v,e[ecnt].nxt = head[u],head[u] = ecnt++;}
void search(int u){
	vis[u] = 1;
	for(int it = head[u];it != -1;it = e[it].nxt)if(!vis[e[it].v]){
		int v = e[it].v;
		search(v);
		dp[u][1] += dp[v][0];
		dp[u][0] += max(dp[v][0],dp[v][1]);
	}
	dp[u][1] += w[u];
}

int main(){
	while(scanf("%d%d",&n,&m) != EOF && n+m){
		ecnt = 0;
		clr(vis,0),clr(dp,0),clr(head,-1),clr(flag,0);
		for(int i = 1;i <= n;++i)scanf("%d",&w[i]);
		for(int i = 1;i <= m;++i)scanf("%d",&x),flag[x] = 1;
		for(int i = 1;i <= n;++i)
			for(int j = 1;j <= n;++j)
				if(flag[abs(w[i]-w[j])])adde(i,j);
		int ret = 0;
		for(int i = 1;i <= n;++i)if(!vis[i])search(i),ret += max(dp[i][0],dp[i][1]);
		cout<<ret<<endl;
	}
	return 0;
}

　　

H - Chores POJ 1949

题意：

有n(<=10000)个任务,如果要完成第i个任务的话,就必须先完成某些任务才能完成任务i,问完成所有任务的最小时间.(题目已经按照拓扑排序排好了并且一段时间可以进行多个任务)

题解：

0.定义状态：dp[v]表示完成任务v需要的最少的时间。

1.状态转移：dp[v] += max{dp[u]}+w[v](u为v的所有先决条件)

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+7;
int maxi,w,m,x,dp[N],n,ret;

int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;++i){
		maxi = 0;
		scanf("%d%d",&w,&m);
		while(m--)scanf("%d",&x),maxi = max(maxi,dp[x]);
		dp[i] += maxi+w;
	}
	for(int i = 1;i <= n;++i)ret = max(ret,dp[i]);
	cout<<ret<<endl;
	return 0;
}

　　

 I - Moo University - Financial Aid POJ 2010

题意：

有n(<=100000)头奶牛,每头奶牛都有分数和它需要的钱,要选择m(奇数)头奶牛,现在有f块钱,使得中间分数的那头奶牛分数尽量高。

题解：

0.首先将这n只奶牛按照分数排序,枚举中间分数的那只奶牛i,那么在[1,i-1]要选择[m/2]只,在[i+1,c]选择[m/2]只。

1.定义状态f[i]表示[1,i]选择奶牛的最小花费,g[i]表示[i,n]选择奶牛的最小花费,那么选择n只奶牛总花费为f[i-1]+g[i+1]+w[i]

2.关于维护f和g,那么就可以用优先队列来进行维护。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 4e5+7;
priority_queue <int> pq;
int n,m,f,S,sum,f[N],g[N];
struct node{
	int v,w;
	bool operator < (const node &rhs)const{return v > rhs.v;}
}x[N];

int main(){
	while(scanf("%d%d%d",&m,&n,&f) != EOF){
		for(int i = 1;i <= n;++i)scanf("%d%d",&x[i].v,&x[i].w);
		sort(x+1,x+1+n);
		
		while(!pq.empty())pq.pop();
		sum = 0,S = m-1>>1;
		for(int i = 1;i <= S;++i)pq.push(x[i].w),sum += x[i].w;f[S] = sum;
		for(int i = S+1;i <= n;++i){
			if(x[i].w < pq.top())sum = sum-pq.top()+x[i].w,pq.pop(),pq.push(x[i].w);
			f[i] = sum;
		}
		
		while(!pq.empty())pq.pop();
		sum = 0,S = m-1>>1;
		for(int i = n;i >= n-S+1;--i)pq.push(x[i].w),sum += x[i].w;g[n-S+1] = sum;
		for(int i = n-S;i >= S;--i){
			if(x[i].w < pq.top())sum = sum-pq.top()+x[i].w,pq.pop(),pq.push(x[i].w);
			g[i] = sum;
		}
		
		bool flag = false;
		for(int i = S+1;i <= n-S;++i)if(f[i-1]+g[i+1]+x[i].w <= f){
			flag = true;printf("%d
",x[i].v);break;
		}
		flag ? 1 : puts("-1");
	}
	return 0;
}

　　

J - Folding POJ 2176

题意：

给出一个字符串,可以对它进行压缩,压缩的规则:①对于重复的字串abcabc可以压缩为2(abc)②对于已经压缩的字符串abcdefg9(k)abccdefg9(k)可以压缩为2(abcdefg9(k)),使得最后的字串的长度最小并输出其最后的形式。

题解：

0.很明显的区间dp,定义状态dp[l][r].L表示在区间[l,r]的最小长度,dp[l][r].S表示区间[l,r]最小长度的字串形式。

1.状态转移：

①：dp[l][r].L = 数字位数+2(两个括号)+k

　　dp[l][r].S = "数字(字符串)"  条件：(如果可以折叠,k表示当前字串的重复长度)

②：dp[l][r].L =  dp[l][k].L+dp[k+1][r].L

      dp[l][r].S = dp[l][k].S+dp[k+1][r].S 条件(dp[l][r].L > dp[l][k].L+dp[k+1][r].L)

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1e9+7;
const int N = 105;
struct dpregister{int l;char str[105];}dp[N][N];
int scnt = 0;
char str[N],ch[N];

int main(){
	scanf("%s",str);
	int n = strlen(str);
	for(int i = 0;i < n;++i)dp[i][i].l = 1,dp[i][i].str[0] = str[i],dp[i][i].str[1] = '';
	for(int len = 2;len <= n;++len){
		for(int l = 0;l+len-1 <= n;++l){
			int r = l+len-1;
			dp[l][r].l = inf;
			for(int k = 1;k < len;++k)if(len%k == 0){
				int q = l+k,p = l;
				while(q <= r){
					if(str[q] != str[p])break;
					p++,q++;
					if(p == l+k)p = l;
				}
				if(q > r){
					int cnt = len/k,scnt = -1;
					while(cnt){ch[++scnt] = cnt%10+'0',cnt /= 10;}
					for(int p = 0;p<<1 <= scnt;++p)swap(ch[p],ch[scnt-p]);
					strcpy(dp[l][r].str,ch);
					dp[l][r].str[++scnt] = '(';
					for(int p = 0;dp[l][l+k-1].str[p];++p)dp[l][r].str[++scnt] = dp[l][l+k-1].str[p];
					dp[l][r].str[++scnt] = ')';
					dp[l][r].l = scnt+1;
					dp[l][r].str[++scnt] = '';
					break;
				}
			}
			for(int k = l;k < r;++k)if(dp[l][r].l > dp[l][k].l+dp[k+1][r].l){
				dp[l][r].l = dp[l][k].l+dp[k+1][r].l;
				strcpy(dp[l][r].str,dp[l][k].str);
				strcat(dp[l][r].str,dp[k+1][r].str);
			}
		}
	}
	printf("%s
",dp[0][n-1].str);
	return 0;
}

　　

K - Naptime POJ 2228

题意：

一天有n(<=3830)个小时,有一只奶牛要睡m个小时,如果从a睡到b那么获得的权值为w[a+1]+w[a+2]+...w[b]并且它可以睡多次但是总的时间不能超过m,但是这一天可能是个环,存在[b,1,a]的情况,求最大获得的权值。

题解：

0.定义状态：dp[i][j][0/1]表示前i个小时,睡了j个小时,当前奶牛是醒/睡着的。

1.因为出现环的本质是因为第1个小时睡并且第n个小时也睡,那么有以下三种情况

状态转移：dp[i][j][0] = max(dp[i-1][j][1],dp[i-1][j][0])

　　　　　dp[i][j][1] = max(dp[i-1][j-1][1]+w[i],dp[i-1][j-1][0])

①第1个小时不睡,那么不会出现环的情况.

边界dp[1][0][0] = 0,dp[1][0][1] = -inf 答案为max{dp[n][m][0],dp[n][m][1])

②第1个小时睡,第n个小时不睡,那么不会出现环的情况

边界dp[1][0][0] = -inf,dp[1][1][1] = 0 答案为dp[n][m][0]

③第1个小时睡,第n个小时也睡,那么最优的情况必定为环

边界dp[1][0][0] = -inf,dp[1][1][1] = w[1],答案为dp[n][m][1]

2.但是3830*3830*2会MLE,所以要滚动起来~~~

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
const int inf = 1e9+7;
int dp[2][N][2],w[N],ret,n,m,c;
#define clr(a,b) memset(a,b,sizeof(a))
void update(){
	c = 1;
	for(int i = 2;i <= n;++i){
		c ^= 1,dp[c][0][0] = 0;
        for(int j = 1;j <= m;j++){  
            dp[c][j][0] = max(dp[c^1][j][0],dp[c^1][j][1]);
            dp[c][j][1] = max(dp[c^1][j-1][1]+w[i],dp[c^1][j-1][0]);  
        }
	}
}

int main(){
	while(scanf("%d%d",&n,&m) != EOF){
		ret = 0;
		for(int i = 1;i <= n;++i)scanf("%d",&w[i]);
	
		clr(dp,128),dp[1][1][1] = 0,dp[1][0][0] = -inf;
		update(),ret = max(ret,max(dp[c][m][0],dp[c][m][1]));
	
		clr(dp,128),dp[1][0][0] = -inf,dp[1][1][1] = 0;
		update(),ret = max(ret,dp[c][m][0]);
	
		clr(dp,128),dp[1][0][0] = -inf,dp[1][1][1] = w[1];
		update(),ret = max(ret,dp[c][m][1]);
	
		cout<<ret<<endl;
	}
	return 0;
}

　　

L - Greatest Common Increasing Subsequence hdu1423

题意：

给出两个长度为n,m(<=1000)的数列A,B,求LCIS。

题解：

0.定义状态:dp[i][j]表示A串前i个数,B串前j个数并且是以B[j]结尾构成的LCIS的长度.

1.状态转移:

①dp[i][j] = max{dp[i-1][k]}+1(a[i] == b[j] && b[j] > b[k])

以上转移复杂度为n^3

但是观察发现(a[i] == b[j] && b[j] > b[k])所以可以得到a[i]>b[k]那么当a[i]>b[j]时维护一个最大值即可

①maxi = max(maxi,dp[i-1][j]) 条件(a[i]>b[j])

②dp[i][j] = maxi+1 条件(a[i] == b[j])

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e3+7;
int T,dp[N][N],A[N],B[N],n,m;

int main(){
	scanf("%d",&T);
	while(T--){
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		for(int i = 1;i <= n;++i)scanf("%d",&A[i]);
		scanf("%d",&m);
		for(int i = 1;i <= m;++i)scanf("%d",&B[i]);
		for(int i = 1;i <= n;++i){
			int maxi = 0,id;
			for(int j = 1;j <= m;++j){
				if(A[i] == B[j])dp[i][j] = maxi+1;
				if(A[i] != B[j]){
					if(A[i]>B[j])maxi = max(maxi,dp[i-1][j]);
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		int ret = 0;
		for(int i = 1;i <= m;++i)ret = max(ret,dp[n][i]);
		cout<<ret<<endl;
		if(T)cout<<endl;
	}
	return 0;
}