1494.txt

杭电acm解题报告2001---2099.

#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;
}

s