USACO Section 3.1 Stamps

Stamps

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

For example, consider stamps whose values are limited to 1 cent and 3 cents; you can use at most 5 stamps. It's easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren't much harder:

  • 6 = 3 + 3
  • 7 = 3 + 3 + 1
  • 8 = 3 + 3 + 1 + 1
  • 9 = 3 + 3 + 3
  • 10 = 3 + 3 + 3 + 1
  • 11 = 3 + 3 + 3 + 1 + 1
  • 12 = 3 + 3 + 3 + 3
  • 13 = 3 + 3 + 3 + 3 + 1.

However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13.

The most difficult test case for this problem has a time limit of 3 seconds.

PROGRAM NAME: stamps

INPUT FORMAT

Line 1: Two integers K and N. K (1 <= K <= 200) is the total number of stamps that can be used. N (1 <= N <= 50) is the number of stamp values.
Lines 2..end: N integers, 15 per line, listing all of the N stamp values, each of which will be at most 10000.

SAMPLE INPUT (file stamps.in)

5 2
    1 3
    

OUTPUT FORMAT

Line 1: One integer, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set.

SAMPLE OUTPUT (file stamps.out)

13
    
Analysis

This problem is also a DP problem. Considering the minimum volumn of a bag that cannot be stored by the K stamps and N kinds of the given stamps, we can find the problem becomes to find the dynamic function to describe it. We call f[i] as the minimum number of stamps to get the value of i, which depends on the minimum of a set of f[i-value[j]]+1),((i-Value[j]>=0 j=1..Stamps).

In order to abbreviate functioning amount, find out the MaxValue, which is the maximum of set Value[i], and all of its multiples can be only fixed with i/MaxValue.

At last,the edge of the problem is when f[k]>maxuse and print k-1.

Code

/*
ID:braytay1
PROG:stamps
LANG:C++
*/

#include 
<iostream>
#include 
<fstream>
#define min(a,b) (a<b)?a:b
using namespace std;


int main(){
    ifstream fin(
"stamps.in");
    ofstream fout(
"stamps.out");
    
int k1,n,max=-1;
    
int s[51];
    
short int f[2000000];
    fin
>>k1>>n;
    
for (int i=1;i<=n;i++{fin>>s[i];max=(max>s[i])?max:s[i];}
    
if (max==1{fout<<max*k1<<endl;return 0;}
    memset(f,
100,sizeof(f));
    f[
0]=0;
    
for (int j=1,k=max;k<=max*k1;k+=max,j++) f[k]=j;
    
int kk;
    
for (kk=1;kk<=max*k1;++kk){
        
if (kk%max==0continue;
        
for (int j=1;j<=n;++j) {
            
if (kk-s[j]>=0
                
if (f[kk-s[j]]+1<f[kk]) f[kk]=f[kk-s[j]]+1;
        }

        
if (f[kk]>k1) break;
    }

    fout
<<kk-1<<endl;
    
return 0;
}


 

posted on 2008-08-22 01:32 幻浪天空领主 阅读(199) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜