C++递推算法

数塔问题

#include<bits/stdc++.h>
using namespace std;
void f(int,int,int);
int a[100][100];
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<1+i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<i+1;j++){
			a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
		}
	}
	cout<<a[0][0];
	return 0;
}
void f(int n){
	
}

摘花生问题

#include<bits/stdc++.h>
using namespace std;
void f(int,int,int sum);
char a[100][100];
int n,ma=-1,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			cin>>a[i][j];
		}
	}
	f(1,1,0);
	cout<<ma;
	return 0;
}
void f(int x,int y,int sum){
	if(x==n&&y==m){
		sum=sum+a[x][y];
		ma=max(ma,sum);
		return;
	}
	if(y+1<=m){
		f(x,y+1,sum+a[x][y]);
	}
	if(x+1<=n) f(x+1,y,sum+a[x][y]);
	return;
}

流感传染

#include<bits/stdc++.h>
using namespace std;
void f(int,int);
char a[100][100];
int n,sum;
int main()
{
	int m;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	cin>>m;
	for(int i=0;i<m;i++){
		f(n,m);
	}
	cout<<sum/2;
	return 0;
}
void f(int n,int m){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='@'){
				if(m==0) sum++;
				if(a[i][j+1]=='.') a[i][j+1]='.';
				if(a[i][j-1]=='.') a[i][j-1]='.';
				if(a[i+1][j]=='.') a[i+1][j]='.';
				if(a[i-1][j]=='.') a[i-1][j]='.';
				sum=sum+4;
			}
		}
	}
}

数塔的行走路径

#include<bits/stdc++.h>
using namespace std;
void f(int);
struct p{
	int x,y;
};
p po[120];
int lp=0;
int a[100][100];
int b[100][100];
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<1+i;j++){
			cin>>a[i][j];
			if(i==n-1){
				b[i][j]=a[i][j];
			}
		}
	}
	int r=0;
	int c=0;
	po[0].x=r;
	po[0].y=c;
	for(int i=1;i<n;i++){
		if(b[r+1][c]>b[r+1][c+1]){
			r++;
			po[i].x=r;
			po[i].y=c;
		}
		else{
			r++;
			c++;
			po[i].x=r;
			po[i].y=c;
		}
	}
	for(int i=n-1;i>=1;i--){
		cout<<po[i].x+1<<','<<po[i].y+1<<"-->";
	}
	cout<<po[0].x+1<<','<<po[0].y+1<<endl;
	cout<<b[0][0];
	return 0;
}
void f(int n){
	
}

摘花生2

#include<bits/stdc++.h>
using namespace std;
void f(int);
struct p{
	int x,y;
};
p k[120];
int lp=0;
int a[100][100];
int b[100][100];
int n;
int main()
{
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(i==0&&j==0){
				b[i][j]=a[i][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1) b[i][j]=b[i][j-1]+a[i][j];
			else if(j==1) b[i][j]=b[i-1][j]+a[i][j];
			else b[i][j]=max(b[i-1][j],b[i][j-1])+a[i][j];
		}
	}
	int r=n,c=m;
	k[lp++]=a[r][c];
	while(true){
		if(r==1&&c==1){
			break;
		}
		if(b[r-1][c]>b[r][c-1]){
			r=r-1;
			k[lp++]=a[r][c];
		}
		else{
			c=c-1;
			k[lp++]=a[r][c];
		}
	}
	for(int i=lp-1;i>=1;i--){
		cout<<k[i]<<"-";
	}
	cout<<k[0];
	return 0;
}
void f(int n){
	
}