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){}