[数据结构与算法]y神动态规划第二课、第三课代码

一、最长上升子序列问题

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int n;
int a[N],f[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	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);
		}
	}
	
	int res=0;
	for(int i=1;i<=n;i++) res=max(res,f[i]);
	printf("%d\n",res);
	
	return 0;
} 

二、怪盗基德的滑翔翼

#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;

int n;
int a[N],f[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<n;i++) scanf("%d",&a[i]);
		
		//正向求解LIS问题
		int res=0;
		for(int i=1;i<=n;i++){
			f[i]=1;
			for(int j=1;j<i;j++)
				if(a[i]>a[j])
					f[i]=max(f[i],f[j]+1);
			res = max(res,f[i]);
		} 
		//反向求解LIS问题
		for(int i=n;i;i--){
			f[i]=1;
			for(int j=n;j>i;j--)
				if(a[i]>a[j])
					f[i]=max(f[i],f[j]+1);
			res = max(res,f[i]);
		} 
		cout<<res<<endl;
	}
}

三、登山问题

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;
int a[N];
int f[N],g[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++)
			if(a[i]>a[j])
				f[i]=max(f[i],f[j]+1);
	}
	
	for(int i=n;i;i--){
		g[i]=1;
		for(int j=n;j>i;j--)
			if(a[i]>a[j])
				g[i]=max(g[i],g[j]+1);
	}
	
	int res=0;
	for(int i=1;i<=n;i++) res=max(res,f[i]+g[i]-1);
	cout<<res<<endl;
	return 0;
}

四、友好城市

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N=5010;

int n;
PII q[N];
int f[N];

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d%d",&q[i].first,&q[i].second);
	sort(q,q+n);//对first从小到大排序，当first相同对second排序 
	
	int res=0;
	for(int i=0;i<n;i++){
		f[i]=1;
		for(int j=0;j<i;j++)
			if(q[i].second>q[j].second)
				f[i]=max(f[i],f[j]+1);
		res=max(res,f[i]);
	}
	cout<<res<<endl;
	return 0;
} 

五、最大上升子序列和

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int n;
int f[N],a[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++){
		f[i]=a[i];
		for(int j=1;j<=i;j++){
			if(a[i]>a[j])
				f[i]=max(f[i],f[j]+a[i]);
		}
	}
	int res=0;
	for(int i=1;i<=n;i++) res=max(res,f[i]);
	cout<<res<<endl;
	return 0;
}

六、拦截导弹

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int n;
int q[N];
int f[N],g[N];

int main(){
	while(cin>>q[n]) n++;
	
	int res=0;
	for(int i=0;i<n;i++){
		f[i]=1;
		for(int j=0;j<i;j++)
			if(q[j]>q[i])
				f[i]=max(f[i],f[j]+1);
			res=max(res,f[i]);
	}
	
	cout<<res<<endl;
	
	int cnt=0;
	for(int i=0;i<n;i++){
		int k=0;
		while(k<cnt&&g[k]<q[i]) k++;
		g[k]=q[i];
		if(k>=cnt) cnt++;
	}
	
	cout<<cnt<<endl;
	
	return 0;
} 

七、导弹防御系统

#include<iostream>
#include<algorithm>

using namespace std;

const int N=55;

int n;
int q[N];
int up[N],down[N];
int ans;

void dfs(int u,int su,int sd){
	if(su+sd>=ans) return;
	if(u==n){
		ans=su+sd;
		return;
	}
	
	//情况1:将当前数放到上升子序列中
	int k=0;
	while(k<su&&up[k]>=q[u]) k++;
	int t=up[k];
	up[k]=q[u];
	if(k<su) dfs(u+1,su,sd);
	else dfs(u+1,su+1,sd);
	up[k]=t;
	
	//情况2：将当前数放到下降子序列中
	k=0;
	while(k<sd&&down[k]<=q[u]) k++;
	t=down[k];
	down[k]=q[u];
	if(k<sd) dfs(u+1,su,sd);
	else dfs(u+1,su,sd+1);
	down[k]=t; 
} 

int main(){
	while(cin>>n,n){
		for(int i=0;i<n;i++) cin>>q[i];
		
		ans=n;
		dfs(0,0,0);
		
		cout<<ans<<endl;
	}
	
	return 0;
}

八、最长公共上升子序列

#include<iostream>
#include<algorithm>

using namespace std;

int N;
int a[N],b[N];
int f[N][N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			f[i][j]=f[i-1][j];
			if(a[i]==b[i]){
				f[i][j]=max(f[i][j],1);
				for(int k=1;k<j;k++){
					if(b[k]<b[j])
						f[i][j]=max(f[i][j],f[i][k]+1);
				}
			}
		}
/*
//优化		
	for(int i=1;i<=n;i++){ 
		int maxv=1; 
		for(int j=1;j<=n;j++){
			f[i][j]=f[i-1][j];
			if(a[i]==b[i]) f[i][j]=max(f[i][j],maxv);
			if(b[j]<a[i]) maxv=max(maxv,f[i][j]+1);
		}
	}
*/
	int res=0;
	for(int i=1;i<=n;i++) res=max(res,f[n][i]);
	
	printf("%d\n",res);
	
	return 0;
}