[DP] 자동차 경주대회 (KOI 1998 초등)

 

#include <stdio.h>
int dp[105];
int dis[105],t[105];
int where[105],ans[105];
int main()
{
    int M,n,sum=0,i,tmp,j,cnt=0;
    scanf("%d",&M);
    scanf("%d",&n);
    for(i=1;i<=n+1;i++)
    {
        scanf("%d",&tmp);
        sum+=tmp;
        dis[i]=sum;
    }
 
    for(i=1;i<=n;i++)
        scanf("%d",&t[i]);
 
    for(i=1;i<=n+1;i++)
    {
        dp[i]=2e8;
        for(j=i-1;j>=0;j--)
        {
            if(dis[i]-dis[j]<=M)
            {
                if(dp[i]>dp[j]+t[i])
                {
                    dp[i]=dp[j]+t[i];
                    where[i]=j;
                }
 
            }
            else
                break;
        }
    }
    i=where[n+1];
    while(i!=0)
    {
        ans[cnt++]=i;
        i=where[i];
    }
 
    printf("%d\n",dp[n+1]);
    printf("%d\n",cnt);
    for(i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);
    return 0;
}
​