uva 709 - Formatting Text

견본을 제출하였는데 다행히 1y라서 다행이다.
dp[i][j]는 i번째 단어가 줄에서 시작하는 위치가 j일 때 가장 작은 나쁜 값임을 나타낸다
두 가지 상황으로 나뉘어 고려한다.
1. 단독 한 줄
2. 앞의 단어나 뒤의 단어와 한 줄
만약 이 문제의 유형이 dp인 것을 모른다면 나는 틀림없이 해낼 수 없을 것이다.(⊙o⊙)

#include <iostream>

#include<cstdio>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

char s[10005],words[10005][85];

int n,top,len[10005],dp[10005][85];



int DP(int i,int j)

{

    if(dp[i][j]!=-1)

    return dp[i][j];

    dp[i][j]=INF;

    if(i==top)

    {

        if(j==0)

        return dp[i][j]=0;

        else

        return dp[i][j];

    }

    //    

    if(j==0)

    dp[i][j]=min(dp[i][j],500+DP(i+1,0));

    //           

    //  

    if(j+len[i]==n)

    return dp[i][j]=min(dp[i][j],DP(i+1,0));

    //  

    else

    {

        //         

        int x=j+len[i]+1;



        for(int k=x;k<n;k++)

        {

            //  k          

            if(k+len[i+1]>n)

            break;

            int t=k-x;

            dp[i][j]=min(dp[i][j],t*t+DP(i+1,k));

        }

    }

    return dp[i][j];

}

void print(int i,int j)

{

    if(i==top)

    {

        puts("");

        return;

    }

    printf("%s",words[i]);

    if(j==0&&dp[i][j]==dp[i+1][0]+500)

    {

        puts("");

        print(i+1,0);

    }

    else if(j+len[i]==n&&dp[i][j]==dp[i+1][0])

    {

        puts("");

        print(i+1,0);

    }

    else

    {

        //         

        int x=j+len[i]+1;



        for(int k=x;k<n;k++)

        {

            //  k          

            if(k+len[i+1]>n)

            break;

            int t=k-x;

            if(dp[i][j]==t*t+dp[i+1][k])

            {

                for(int i=0;i<=t;i++)

                putchar(' ');

                print(i+1,k);

                break;

            }

        }

    }

}

int main()

{

    while(scanf("%d",&n),n)

    {

        getchar();

        top=0;

        while(gets(s))

        {

            if(!s[0])

            break;

            int i=0;

            for(;s[i]==' ';i++);

            for(;s[i];)

            {

                sscanf(s+i,"%s",words+top);

                for(;s[i]!=' '&&s[i];i++);

                for(;s[i]==' ';i++);

                len[top]=strlen(words[top]);

                top++;

            }

        }

        len[top]=0;

        memset(dp,-1,sizeof(dp));

        DP(0,0);

        print(0,0);

    }

    return 0;

}