连接

这道题一开始我想错了以为是贪心。。。

当时看到这道题的思路就是首先要-5然后用DP最后用看剩下来谁最大就买谁~

后来实在不知道应该怎么处理，终不能用VIS来跟踪标记把= =。。。然后觉得思路错了， 应该是吧最大的那个菜留到最后再买~

1 #include 
      
        2 #include 
       
         3 /*int cmp(const void *a,const void *b) 4 { 5     return a-b; 6 }*/ 7 int main() 8 { 9     int t,n,i,j;10     int dp[10005],val[1005];11     int sum;12     while(scanf("%d",&n)&&n)13     {14         int maxi = 0;15         for(i = 0;i < n;i++)16         {17             scanf("%d",val+i);18             if(val[maxi] < val[i])19             maxi = i;20         }21 22         scanf("%d",&sum);23        // qsort(val,n,sizeof(int),cmp);24        if(sum >= 5)25        {26            memset(dp,0,sizeof(dp));27             for(i = 0;i < n;i++)28             {29                 if(i != maxi)30                 for(j = sum-5;j >= val[i];j--)31                 if(dp[j] < dp[j-val[i]]+val[i])32                 dp[j] = dp[j-val[i]]+val[i];33             }34             printf("%d\n",sum-dp[sum-5]-val[maxi]);35        }36        else37        printf("%d\n",sum);38     }39     return 0;40 }