POJ-2609-듀얼 타워 dp

제목의 뜻: n대의 자동차가 배에 실어야 한다. 배에는 두 개의 갑판 A, B가 있다. 길이는 모두 L이다. n대의 자동차는 반드시 한 번에 올라가야 한다. 최대 몇 대의 차를 실을 수 있느냐고 묻는다.
제목 해석: 미리 처리 접두사와 dp[i][j]를 정의하여 앞의 i대의 차를 표시하고 A갑판의 길이는 j가 조건을 충족시킬 수 있는지를 나타낸다. 이렇게 상태가 이동할 때 그가 A나 B로 운반될 수 있는지만 고려해야 한다.
AC 코드:

#include
#include
#include
using namespace std;
int n,len,a[510],dp[510][10010],pre[510][10010],sum[510];
void dis(int x,int y)
{
    if(x<=0)    return ;
    if(pre[x][y]==1)
    {
        dis(x-1,y-a[x]);
        printf("port
");
    }
    else
    {
        dis(x-1,y);
        printf("starboard
");
    }
}
int main()
{
    while(scanf("%d",&len)!=EOF)
    {
        len*=100;
        n=1;
        while(scanf("%d",&a[n])&&a[n])
        {
            n++;
        }
        n--;
        sum[0]=0;
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i];
        memset(dp,0,sizeof(dp));
        memset(pre,-1,sizeof(pre));
        dp[0][0]=1;
        int ans=0,tar;
        for(int i=1;i<=n;i++)
        {
            for(int j=len;j>=0;j--)
            {
                if(sum[i-1]-j>len)    break;
                if(sum[i]-j<=len)
                {
                    if(j-a[i]>=0)
                        dp[i][j]=dp[i-1][j]|dp[i-1][j-a[i]];
                    else
                        dp[i][j]=dp[i-1][j];
                    if(dp[i-1][j])
                        pre[i][j]=0;
                    else if(j-a[i]>=0&&dp[i-1][j-a[i]])
                        pre[i][j]=1;
                }
                else if(j-a[i]>=0)
                {
                    dp[i][j]=dp[i-1][j-a[i]];
                    pre[i][j]=1;
                }
                if(dp[i][j])
                {
                    ans=i;
                    tar=j;
                }
            }
            if(ans!=i)
                break;
        }
        printf("%d
",ans);
        if(ans)
            dis(ans,tar);
    }
    return 0;
}