另一道线性dp水题
1 #include<set> 2 #include<map> 3 #include<list> 4 #include<queue> 5 #include<stack> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<vector> 10 #include<bitset> 11 #include<memory> 12 #include<utility> 13 #include<cstdio> 14 #include<sstream> 15 #include<iostream> 16 #include<cstdlib> 17 #include<cstring> 18 #include<algorithm> 19 using namespace std; 20 21 int n,m,ans; 22 int a[105][105],f[105][105]; 23 24 int mi(int a,int b){return a<b?a:b;} 25 int ma(int a,int b){return a>b?a:b;} 26 27 int main(){ 28 scanf("%d%d",&n,&m); 29 for(int i=1;i<=n;i++){ 30 for(int j=1;j<=m;j++){ 31 scanf("%d",&a[i][j]); 32 } 33 } 34 for(int i=1;i<=n;i++){ 35 for(int j=1;j<=m;j++){ 36 f[i][j]=(a[i][j]==1?mi(f[i-1][j],mi(f[i-1][j-1],f[i][j-1]))+a[i][j]:f[i][j]); 37 ans=ma(ans,f[i][j]); 38 } 39 } 40 printf("%d ",ans); 41 return 0; 42 }