lilili

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
789 B
2
Indexable
Never
#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;}