lilili
unknown
c_cpp
4 years ago
789 B
5
Indexable
#include<iostream> #include<vector> #include<climits> using namespace std; int main(){ int n; cin>>n; int matrix[n+1][n+1],dp[n+1][n+1]; for(int i=0;i<=n;i++){dp[0][i]=INT_MIN; dp[i][0]=INT_MIN;} for(int i=1;i<=n;i++){for(int k=1;k<=n;k++)cin>>matrix[i][k];} dp[0][1]=0; for(int i=1;i<=n;i++){for(int k=1;k<=n;k++) {dp[i][k]=max(dp[i][k-1],max(dp[i-1][k],dp[i-1][k-1]))+matrix[i][k];}} cout<<dp[n][n]<<endl; int x=n,y=n; vector<string>ans; while(x!=1||y!=1) {ans.push_back(to_string(x)3+","+to_string(y)); if(dp[x][y-1]>dp[x-1][y]){ if(dp[x][y-1]>dp[x-1][y-1])y--; else { x--; y--; } } else { if(dp[x-1][y]>dp[x-1][y-1])x--; else{ x--; y--; } } } cout<<"1,1 "; for(int i=ans.size()-1;i>=0;i--)cout<<"-> "<<ans[i]; return 0;}
Editor is loading...