首页 > ACM题库 > HDU-杭电 > hdu 4104-discount-递推-[解题报告]hoj
2015
04-16

hdu 4104-discount-递推-[解题报告]hoj

Discount

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1073    Accepted Submission(s): 646

Problem Description


All the shops use discount to attract customers, but some shops doesn’t give direct discount on their goods, instead, they give discount only when you bought more than a certain amount of goods. Assume a shop offers a 20% off if your bill is more than 100 yuan,
and with more than 500 yuan, you can get a 40% off. After you have chosen a good of 400 yuan, the best suggestion for you is to take something else to reach 500 yuan and get the 40% off.
For the customers’ convenience, the shops often offer some low-price and useful items just for reaching such a condition. But there are still many customers complain that they can’t reach exactly the budget they want. So, the manager wants to know, with the
items they offer, what is the minimum budget that cannot be reached. In addition, although the items are very useful, no one wants to buy the same thing twice.
 

Input
The input consists several testcases.
The first line contains one integer N (1 <= N <= 1000), the number of items available.
The second line contains N integers Pi (0 <= Pi <= 10000), represent the ith item’s price.

 

Output
Print one integer, the minimum budget that cannot be reached.
 

Sample Input
4 1 2 3 4
 

Sample Output
11
 

Source
 

Recommend
lcy
 

题意:

给你n个基本值。问你这个n个基本值不能组合得到最小的值。每个基本值只能使用一次。

思路:

开始想用01背包做。可惜内存开不下。果断去啃线段树去了。。。思维的深度还不够。。

数学归纳法。我们假定。前i个基本值已经能够1->sum范围的值了。现在加入a[i+1]。

如果a[i+1]>sum+1那么可以肯定前i+1个基本值不能组合得到sum+1。

否侧可以表示出1->sum+a[i+1]的值。因为假如要表示v>sum。那么v-a[i+1]正好在1->sum范围内。

所以可以先对基本值排序。然后递推。排序是为了找到最小的不能表示的值。

详细见代码:

#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;

int a[1010];
int main()
{
    int i,n,sum;

    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
            scanf("%d",a+i);
        sort(a,a+n);
        sum=0;
        for(i=0;i<n;i++)
        {
            if(sum+1<a[i])
                break;
            else
                sum+=a[i];
        }
        printf("%d\n",sum+1);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c