HDU 2159 DP 二维费用

#include<stdio.h>
#include<string.h>
const int max_n=101;
const int INF=9999;
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int dp[max_n][max_n];
    int exp[max_n];
    int ren[max_n];
    int n,m,k,s;
    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
    {
        int i;
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&exp[i],&ren[i]);
        }
        memset(dp,0,sizeof(dp));
        for(i=0;i<k;i++)
        {
            for(int p=1;p<=s;p++)
            {
                for(int j=ren[i];j<=m;j++)
                {
                    dp[p][j]=max(dp[p][j],dp[p-1][j-ren[i]]+exp[i]);
                }
            }
        }
        for(i=0;i<=m;i++)
        {
            if(dp[s][i]>=n)
                break;
        }
        if(i>m) printf("-1\n");
        else printf("%d\n",m-i);


    }
    return 0;
}

#include<stdio.h>
#include<string.h>
const int max_n=101;
const int INF=9999;
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int dp[max_n][max_n];
    int exp[max_n];
    int ren[max_n];
    int n,m,k,s;
    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
    {
        int i;
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&exp[i],&ren[i]);
        }
        memset(dp,0,sizeof(dp));
        for(i=0;i<k;i++)
        {
            for(int p=1;p<=s;p++)
            {
                for(int j=ren[i];j<=m;j++)
                {
                    dp[p][j]=max(dp[p][j],dp[p-1][j-ren[i]]+exp[i]);
                }
            }
        }
        for(i=0;i<=m;i++)
        {
            if(dp[s][i]>=n)
                break;
        }
        if(i>m) printf("-1\n");
        else printf("%d\n",m-i);


    }
    return 0;
}