dp 0pts 求助
查看原帖
dp 0pts 求助
602367
zhaoxuchun楼主2022/10/21 18:35
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],f[1005][1005];
inline void readint(int &x){
	x=0;
	short flag=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=flag;
}
inline void writeint(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) writeint(x/10);
	putchar(x%10+'0');
}
void dfs(int x,int y){
	if(x==1&&y==1){
		dfs(x+1,y);
		dfs(x,y+1);
	}else if(x==n&&y<m){
		f[x][y]=f[x-1][y]+f[x][y];
		dfs(x,y+1); 
	}else if(y==m&&x<n){
		f[x][y]=f[x][y-1]+f[x][y];
	}else if(x==n&&y==m){
		f[x][y]=max(f[x-1][y],f[x][y-1])+f[x][y];
		return;
	}else{
		f[x][y]=max(f[x-1][y],f[x][y-1])+f[x][y];
	}
}
int main(){
	readint(n);
	readint(m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			readint(a[i][j]);
			f[i][j]=a[i][j];
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			if(i==n&&j==m){
//				f[i][j]=max(f[i-1][j]+f[i][j],f[i][j-1]+f[i][j]);
//			}
//			if(i==n&&j<m){
//				f[i][j]=f[i-1][j]+f[i][j];
//			}else if(j==m&&i<n){
//				f[i][j]=f[i][j-1]+f[i][j];	
//			}else{
//				f[i][j]=max(f[i-1][j]+f[i][j],f[i][j-1]+f[i][j]);
//			}
//		}
//	}
//	cout<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<f[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	dfs(1,1);
	writeint(f[n][m]);
	return 0;
} 
2022/10/21 18:35
加载中...