HDU 2546 饭卡

#include  
#include  
#include  
using namespace std;  
#define N 1005  
int dp[N];  
int a[N];  
int dp1[N];  
int main(){  
    int n,m;  
    int maxx;  
    int mm;  
    while(scanf("%d",&n)!=EOF){  
        memset(dp1,0,sizeof(dp1));  
        if(n==0)break;  
        int sum=0;  
        maxx=0;  
        int v=0;  
        for(int i=1;i<=n;i++){  
            scanf("%d",&dp[i]);  
            sum+=dp[i];  
            if(dp[i]>maxx){  
                maxx=dp[i];  
                v=i;  
            }  
        }  
        scanf("%d",&m);  
        if(m<5){  
            printf("%d\n",m);  
            continue;  
        }  
        mm=m;  
        if(n==1){  
            printf("%d\n",m-dp[1]);  
            continue;  
        }  
        if(m-sum>





=5){  
            printf("%d\n",m-sum);  
            continue;  
        }  
        int k=1;  
        for(int i=1;i<=n;i++){  
            if(i!=v){  
                a[k]=dp[i];  
                k++;  
            }  
        }  
        m=m-5;  
        if(m<=0){  
            printf("%d\n",mm-maxx);  
            continue;  
        }  
        for(int i=1;i<=n-1;i++){  
            for(int j=m;j>=a[i];j--){  
                dp1[j]=max(dp1[j],dp1[j-a[i]]+a[i]);  
            }  
        }  
        printf("%d\n",mm-dp1[m]-maxx);  
    }  
    return 0;  
}