最佳路径

ice_pick

#include<bits/stdc++.h>
using namespace std;
int cnt,maxn=0,n,a[101][101]={0};
struct dfs_1
{
        int x;
        int y;
}p[100],p2[100];

int dfs(int c,int x,int y)
{
        for(int i=0;i<2;i++)
        {
               
                p[c].x=x+1;
                p[c].y=y+i;
                cnt+=a[p[c].x][p[c].y];
                if(c==n)
                {
                        if(cnt>maxn)
                        {
                                maxn=cnt;
                                memcpy(p2,p,sizeof(p));
                        }
               
                }
                else
                {
                        dfs(c+1,p[c].x,p[c].y);
                }
                cnt=cnt-a[p[c].x][p[c].y];       
        }
}
int main()
{
        cin>>n;
        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<=i;j++)
                {
                        cin>>a[i][j];
                }
        }
        cnt=a[1][1];
        p[1].x=1;
        p[1].y=1;
        dfs(2,1,1);
        cout<<maxn<<endl;
        for(int i=1;i<=n;i++)
        {
                        cout<<p[i].x<<" "<<p[i].y;
                        cout<<endl;
        }
//        for(int i=1;i<=n;i++)
//        {
//                dp[n][i]=a[n][i];
//        }
//        for(int i=n-1;i>=1;i--)
//        {
//                for(int j=1;j<=i;j++)
//                {
//                        dp[i][j]=max(dp[i+1][j+1],dp[i+1][j])+a[i][j];
//                        cout<<dp[i][j]<<" ";
//                }
//                cout<<endl;
//        }
//        cout<<dp[1][1];
//        dp[1][1]=a[1][1];
//        for(int i=2;i<=n;i++)
//        {
//                for(int j=1;j<=i;j++)
//                {
//                        dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
//                        //cout<<dp[i][j]<<" ";
//                }
//                //cout<<endl;
//        }
//        for(int i=1;i<=n;i++)
//        {
//                if(dp[n][i]>=maxn)
//                {
//                        maxn=dp[n][i];
//                }
//        }
//        cout<<maxn;
        return 0;
}