1494 跑跑卡丁车 .cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <stdio.h>
#include <memory.h>

int l,n;
int a[110],b[110];

int dp[11000][30],it;
inline bool OneLess(int s,int t)
{
	if(s==0)
		return false;
	else
		return s<t;
}

int main()
{
    int i,j,k;
    int len,kt;
	
    while(scanf("%d %d",&l,&n)==2)
    {
        for(i=1;i<=l;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=l;i++)
            scanf("%d",&b[i]);
		
        memset(dp,0,sizeof(dp));
        
		len=0;
		dp[0][0]=1;
		
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=l;j++)
            {
                for(k=0;k<30;k+=2)
				{
					if(dp[len][k]>0)
					{
						if(k>=10)
						{
							dp[len+1][k-10] = OneLess(dp[len+1][k-10] , dp[len][k]+b[j]) ? dp[len+1][k-10] : dp[len][k]+b[j];
						}
						if(k+2>=30)
							kt=20;
						else
							kt=k+2;
						dp[len+1][kt] = OneLess(dp[len+1][kt] , dp[len][k]+a[j]) ? dp[len+1][kt] : dp[len][k]+a[j];
						
						//printf("%d(%d,%d)=%d\n",j,len,k,dp[len][k]);
					}
				}
				len++;
            }//for j
        }//for i

        it=0x7fffff;
        for(i=0;i<30;i+=2)
            if(dp[len][i]>0 && dp[len][i]<it)
                it=dp[len][i];
			
			printf("%d\n",it-1);
    }
    return 0;
}