sgu 104 Little Shop of Flowers Dynamic Planning(dp) 문제

#include <stdio.h>
#include <string.h>
#define INF 0x7fffffff
int n,m,e[101][101],f[101][101];
int c[101][101];
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int i,j,k,u;
		for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            scanf("%d",&e[i][j]);
        memset(f,0,sizeof(f));
        memset(c,0,sizeof(c));
        for(i=1;i<=m;i++)
        {
            f[1][i]=e[1][i];
            c[1][i]=i;
        }
        for(i=2;i<=n;i++)
        {
            for(j=i;j<=m;j++)
            {
                int max=-INF;
                for(k=1;k<j;k++)
                    if(f[i-1][k]>max)
                    {
                        max=f[i-1][k];
                        u=k;
                    }
                f[i][j]=max+e[i][j];
                c[i][j]=u;
            }
        }
        int max=-INF;
        for(i=1;i<=m;i++)
            if(f[n][i]>max)
            {
                max=f[n][i];
                u=i;
            }
        printf("%d
",max);
        i=n;
        int s[101];
        while(i>=1)
        {
            s[i]=u;
            u=c[i][u];
            i--;
        }
        printf("%d",s[1]);
        for(i=2;i<=n;i++)
            printf(" %d",s[i]);
        printf("
");
	}
	return 0;
}
/*
  n  ，m   
     i     j         。
           ，     ，                  

dp 
f[i][j]   i     j    ，       
*/