三默网

  • 三默网为您带来有关“NOJ-算法设计实验4”的文章内容，供您阅读参考。

    NOJ-算法设计实验4

    2023-01-21 17:17:41

    先补作业，再补题解。（有缘补题解QAQ）

    A-最长公共子序列

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
char s[maxn],t[maxn];int lens,lent,dp[maxn][maxn];
int max(int x,int y){
	if(x>=y)return x;
	return y;
}
int main(){
	cin>>s+1>>t+1;
	lens=strlen(s+1);lent=strlen(t+1);
	for(int i=1;i<=lens;i++){
		for(int j=1;j<=lent;j++){
			if(s[i]==t[j]){
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<dp[lens][lent]<<endl;
	return 0;
}

    B-防卫导弹

    lower_bound(dp+1,dp+1+n,h[i])dp[]中第一个>=h[i]的下标
    upper_bound(dp+1,dp+1+n,h[i])dp[]中第一个>h[i]的下标
    lower_bound(dp+1,dp+1+n,h[i],greater< int >())dp[]中第一个<=h[i]的下标 greater< int >() == cmp(int x,int y){return x>y}
    upper_bound(dp+1,dp+1+n,h[i],greater< int >())dp[]中第一个<h[i]的下标

    greater< int >()表示内置类型从大到小排序，比如说原序列是1，2，4，7，15，34，在greater< int >()的表示下，
    1>2>4>7>15>34,lower_bound(num,num+6,7,greater< int >()) 返回greater< int >序列下第一个大于或等于被查数7的值，
    即4；也就是返回的是原序列的中第一个小于或等于被查数7的值

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,h[maxn],dp[maxn];
int max(int x,int y){
	if(x>=y)return x;
	return y;
}
int cmp(int x,int y){
	return x>y;
}
int main(){
	int i;
	while(1){
		cin>>n;
		if(n==0)break;
		for(i=1;i<=n;i++)cin>>h[i],dp[i]=0;
		int ans=0;
		for(i=1;i<=n;i++){
			int t=upper_bound(dp+1,dp+1+n,h[i],cmp)-dp;
			dp[t]=h[i];
			ans=max(ans,t);
		}
		cout<<ans<<endl;		
	}
	return 0;
}

    C-田忌赛马(tian ji racing)

    如果田忌最快的马快于齐王最快的马，就PK
    如果田忌最快的马慢于齐王最快的马：
    如果田忌最慢的马快于齐王的最慢的马，PK
    否则就田忌最慢的马PK齐王最快的马（反正都是输）

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,a[maxn],b[maxn];
int main(){
	int i;
	while(1){
		cin>>n;
		if(n==0)break;
		for(i=1;i<=n;i++)cin>>a[i];
		for(i=1;i<=n;i++)cin>>b[i];
		sort(a+1,a+1+n);sort(b+1,b+1+n);
		int opt1=1,opt2=1,up1=n,up2=n,win=0,lose=0;
		while(up1>=opt1){
			if(a[up1]>b[up2])win++,up1--,up2--;
			else {
				if(a[opt1]>b[opt2])win++,opt1++,opt2++;
				else if(a[opt1]<b[up2])lose--,opt1++,up2--;
				else opt1++,up2--;
			}
		}
	//	cout<<win<<' '<<lose<<endl;
		cout<<win+lose<<endl;
	}
	return 0;
}

    D-计算矩阵连乘积

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,p[maxn],q[maxn],dp[maxn][maxn];
int min(int x,int y){
	if(x<=y)return x;
	return y;
}
int main(){
	cin>>n;
	memset(dp,0x3f3f3f3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>p[i]>>q[i];
		dp[i][i]=0;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n;l++){
			int r=l+len-1;
			for(int m=l;m<=r-1;m++){
				dp[l][r]=min(dp[l][r],dp[l][m]+dp[m+1][r]+p[l]*q[m]*q[r]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}

    E-石子合并

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=200+50;
int a[maxn],n,dp[maxn][maxn],sum[maxn];
int min(int x,int y){
	if(x<=y)return x;
	return y;
}
int main(){
	while(1){
		int i;
		cin>>n;
		if(n==0)break;
		memset(dp,0x3f3f3f3f,sizeof(dp));
		for(i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i],dp[i][i]=dp[i+n][i+n]=0;
		for(i=1;i<=n;i++)sum[i+n]=sum[i+n-1]+a[i]; 
		for(int len=2;len<=n;len++){
			for(int l=1;l<=2*n-len+1;l++){
				int r=l+len-1;
				for(int m=l;m<=r-1;m++){
					dp[l][r]=min(dp[l][r],dp[l][m]+dp[m+1][r]+sum[r]-sum[l-1]);
				}
			}
		}//len从2到n 更新 
		int ans=0x3f3f3f3f;
		for(i=1;i<=n;i++){
			ans=min(ans,dp[i][i+n-1]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

    F-旅游预算

    ps:注意油量超过一半并且可以到达下一个点不加油！

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
struct Node{
	double w,d;
}a[maxn]; 
double s,v,p,dp[maxn];int n,pre[maxn],t[maxn];
double min(double x,double y){
	if(x<=y)return x;
	return y;
}
int main(){
	int i,j;
	cin>>s>>v>>p>>dp[0]>>n;
	for(i=1;i<=n;i++)cin>>a[i].d>>a[i].w,dp[i]=1e9;
	double road=v*p;
	for(i=1;i<=n;i++){
		for(j=0;j<=i-1;j++){
			if(a[i].d-a[j].d>road||(a[i].d-a[j].d)*2<road)continue;//注意油量超过一半并且可以到达下一个点不加油！ 
			double ned=(a[i].d-a[j].d)/p;
			if(dp[i]>dp[j]+ned*a[i].w+2){
				dp[i]=dp[j]+ned*a[i].w+2;
				pre[i]=j;
			}
		}
	}
	double ans=0x3f3f3f3f;int last=0,tot=0;
	for(i=0;i<=n;i++){
		if(road<s-a[i].d)continue;
		if(ans>dp[i]){
			ans=dp[i];
			last=i;
		}
	}
	while(last!=0){
		t[++tot]=last;
		last=pre[last];
	}
	printf("%.2lf %d\n",ans,tot);
	for(i=tot;i>=1;i--)cout<<t[i]<<' ';cout<<endl;
	return 0;
}

    G-花生米（二）

    博弈论：
    定义： jerry后手胜利 为胜利状态。
    10以内的必胜状态：1,3,5,7,9.
    由于可以一次拿10个，我们需要考虑10周围的情况:11为必胜 。
    什么才是必败态？
    当前面i-1,i-5,i-10这10个状态都是必胜态的时候， i一定是必败态。
    否则 i就有机会成为必胜态。
    dp[i]=1表示i是必胜态。

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,dp[maxn];
int main(){
	dp[1]=1;dp[3]=1;dp[5]=1;dp[7]=1;dp[9]=1;dp[11]=1;
	for(int i=12;i<=1000;i++){
		if(dp[i-1]&&dp[i-5]&&dp[i-10])dp[i]=0;
		else dp[i]=1;
	}
	while(1){
		cin>>n;
		if(n==0)break;
		if(dp[n])cout<<0<<endl;
		else cout<<1<<endl;
	}
	return 0;
}

    H-花生米（三）

    dp[i][j]==0：Jerry后手且此时剩余i个当前可取j个并且是必胜态

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,dp[maxn][maxn];
int min(int x,int y){
	if(x<=y)return x;
	return y;
}
int dfs(int res,int c){
	int i;
	if(res==1){
		dp[res][c]=0;
		return 0;
	}
	else if(dp[res][c]!=-1)return dp[res][c];
	int sign=1;
	for(i=1;i<=min(res,c);i++){
		sign=sign&dfs(res-i,2*i);//下一个dfs就是Jerry先手的状态了，必须全部为1，才能使得当前dfs中的为后手必胜 
		if(sign==0)break;
	}
	dp[res][c]=0;
	if(sign==0)
	dp[res][c]=1;
	return dp[res][c];
}
int main(){
	int i,j;
	while(1){
		cin>>n;
		if(n==0)break;
		for(i=0;i<=1000;i++){
			for(j=0;j<=1000;j++){
				dp[i][j]=-1;
			}
		}
		cout<<dfs(n,1)<<endl;
	}
}

    I-花生米（四）

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+50;
int n,a[maxn];
int main(){
	while(1){
		cin>>n;
		if(n==0)break;
		int sum=0,cnt=0,tot=0; 
		for(int i=1;i<=n;i++){
			cin>>a[i],sum+=a[i];
			if(a[i]==1)cnt++;
		}
		if(n==1){
			cout<<0<<endl;
		}
		else if(cnt==n){
			if(n%2==0)cout<<0<<endl;
			else cout<<1<<endl;
		}
		else{
			if(n==2){
				if(a[1]==a[2])cout<<0<<endl;//对称取 
				else cout<<1<<endl;//Tom先手先让a[1]==a[2]，Tom对称取，Jerry必败，所以Jerry必须先手 
			}
			else{
				int sign1=0,sign2=0;	
				if(cnt>0&&cnt%2==0)sign1=0;//只含1个花生米的堆数为偶数 
				else sign1=1;
				if((n-cnt)%2==0)sign2=0;//含>1个花生米的堆数为偶数 
				else sign2=1; 
				if(sign1&&sign2)cout<<1<<endl;//全奇数堆先手必胜，所以Jerry必须先手：比如1 1 1 3 3 3-->1 3 3 3先手必胜 （后手无法赢） 
				else cout<<0<<endl;//如果存在偶数堆，则让对手取成全奇，在此之前，Jerry保持非全奇 
				//如果1 1 1 1 3 3 3 3 .如果先手选3，后手跟着选3，直到3用完，先手选择1，后手到达必胜态
				//如果 先手选3中的2，-->1 1 1 1 1 3 3 3 后手选 1-->1 1 1 1 3 3 3,直到3用完，先手选择1，后手到达必胜态。
				//同理1 1 1 3 3 3 3类型和1 1 1 1 3 3 3类型。 
				//注意 7 3 3 3 3 3 3 3 这种类型即cnt==0，这个时候sign1=1，sign=1，就是指只存在奇数堆，先手必胜。 
			}
		}
	}
	return 0;
} 
/*7
3 3 3 3 3 3 3
*/
//Jerry 后手必胜的条件：后手且吃掉最后的花生米，则Jerry无法后手胜利。

    J-花生米（五）

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+50;
int dp[maxn];
int dfs(int res,int c){
	int i;
	if(res<c){
		dp[res]=0;
		return dp[res];
	}
	if(dp[res]!=-1)return dp[res];
	int sign=1;
	for(i=c;i<=3*c;i++){
		if(res<i)break;
		sign&=dfs(res-i,c+i);
		if(sign==0)break;
	}
	dp[res]=0;
	if(!sign)dp[res]=1;
	return dp[res];
}
int main(){
	int tot=0;
	while(1){
		int i;
		double x;
		cin>>x;
		if(x<0)break;
		for(i=0;i<=x*10;i++){
			dp[i]=-1;
		}
		int w=x*10;
		cout<<1-dfs(w-10,10)<<endl;
	}
	return 0;
}

    K-装盘子

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100+50;
int n,m,dp[maxn][maxn];
int dfs(int resn,int resm){
	if(resn==1||resm==1||resm==0)return 1;
	if(dp[resn][resm])return dp[resn][resm];
	int ans=0;
	if(resm<resn)ans=dfs(resm,resm);
	else ans=dfs(resn-1,resm)+dfs(resn,resm-resn);
	dp[resn][resm]=ans;
	return ans;
}
int main(){
	cin>>m>>n;
	cout<<dfs(n,m)<<endl;
	return 0;
}

    L-滑雪

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=200+50;
int n,m,h[maxn][maxn],dp[maxn][maxn];
int max(int x,int y){
	if(x>=y)return x;
	return y;
}
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int x,int y){
	if(dp[x][y])return dp[x][y];
	dp[x][y]=1;
	int sign=0,ans=0,i;
	for(i=0;i<4;i++){
		int nexx=x+d[i][0],nexy=y+d[i][1];
		if(nexx>=1&&nexx<=n&&nexy>=1&&nexy<=m&&h[nexx][nexy]>h[x][y])sign++,ans=max(ans,dfs(nexx,nexy)+1);
	}
	if(!sign)dp[x][y]=1;
	else dp[x][y]=ans;
	return dp[x][y];
}
int main(){
	cin>>n>>m;
	int i,j,k,maxx=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>h[i][j];
		}
	}
	int ans=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			ans=max(ans,dfs(i,j));
		}
	}
	cout<<ans<<endl;
	return 0;
}

  • 上一篇：zookeeper启动报错:java.io.EOFException
  • 下一篇：nginx代理java websocket引发的EOFException
  • NOJ-算法设计实验-test3
  • NOJ-算法设计实验4
  • 算法分析与设计实验-游艇租用问题
  • 简单算法问题（Swift4）
  • 算法设计与分析: 4-23 最优分解问题
  • 编写算法对输入的一个整数，判断它能否被4、7、9整数
  • OpenCV算法加速（4）官方源码v4.5.5的默认并行加速的编译选项是什么？
  • 算法4-1.1.10下面这段代码有什么问题
  • 算法4 符号表
  • 《算法4》符号表以及二叉查找树

    • iOS最新文章

    标签

    

    网站地图

    Copyright © 2019-2022 三默网