URAL1029[Ministry]

动态规划。(又见VIJOS1139)


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-20


DESCRIPTION:


VIJOS P1139


*/


#include <iostream>


using namespace std;


 


int F[1024];


int room[1024][1024];


int level[1024][1024];


int out[1024*1024];


int m,n;


 


int main()


{


    cin>>m>>n;


   


    for (int i=m;i>=1;i–)


    {


            int p[1024];


            for (int j=1;j<=n;j++)


            {


                cin>>p[j];


                F[j]+=p[j];


                room[i][j]=j;


                level[i][j]=i+1;


            }


            for (int j=2;j<=n;j++)


                if (F[j]>F[j-1]+p[j])


                {


                   F[j]=F[j-1]+p[j];


                   room[i][j]=j-1;


                   level[i][j]=i;


                }


            for (int j=n-1;j>=1;j–)


                if (F[j]>F[j+1]+p[j])


                {


                   F[j]=F[j+1]+p[j];


                   room[i][j]=j+1;


                   level[i][j]=i;


                }


    }


   


    int n1=1;


    for (int i=n;i>1;i–)


        if (F[i]<F[n1])


           n1=i;


    int k=0;


    for (int m1=1;m1!=m+1😉


    {


        out[k++]=n1;


        int m2=level[m1][n1];


        int n2=room[m1][n1];


        m1=m2;


        n1=n2;


    }


    for (int i=k-1;i>=0;i–)


        cout<<out[i]<<char(i?’ ‘:’\n’);


    //while (cin.get());


    return 0;


}