246
京東網上商城
[usaco]3.1.5 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
---------------------------
這個題的要點是使用索引，因為最終的結果值可能非常大，如果使用空間不善的話，會超出係統給出的值。
通過動態規劃，計算某個值要使用的最少的stamp數目，來自於i-value[x]的的stamp數目。
關鍵點在這裏：
for(int i=0;;i++)
{
if(results[INDEX(i)]>k)
{
ptr=i;
break;
}
for(int j=0;j<n;j++)
{
if(results[INDEX(i+values[j])]==-1||((results[INDEX(i+values[j])])>(results[INDEX(i)]+1)))
results[INDEX(i+values[j])]=results[INDEX(i)]+1;
}
results[INDEX(i)]=-1;
}
這道題目我提交了6次，就是因為剛開始估計使用空間時失誤，沒想到結果會那麼大。後來隻好采用索引了。
采用索引之後使用的空間可能會很小，但也不好說每一個周期需要多少，隻好采用一個很大的值。
我的程序最終結果，最複雜的一個結果使用的時間才0.6s，遠遠小於係統提供的最大時間3s：
USER: Ma yunlei [yunleis2]
TASK: stamps
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3412 KB]
Test 2: TEST OK [0.000 secs, 3412 KB]
Test 3: TEST OK [0.000 secs, 3412 KB]
Test 4: TEST OK [0.000 secs, 3412 KB]
Test 5: TEST OK [0.000 secs, 3412 KB]
Test 6: TEST OK [0.000 secs, 3412 KB]
Test 7: TEST OK [0.000 secs, 3412 KB]
Test 8: TEST OK [0.000 secs, 3412 KB]
Test 9: TEST OK [0.000 secs, 3412 KB]
Test 10: TEST OK [0.081 secs, 3412 KB]
Test 11: TEST OK [0.648 secs, 3412 KB]
Test 12: TEST OK [0.135 secs, 3412 KB]
Test 13: TEST OK [0.000 secs, 3412 KB]
All tests OK.
Your program ('stamps') produced all correct answers! This is your
submission #6 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 ----
5 2
1 3
------- test 2 ----
1 4
1 2 3 5
------- test 3 ----
2 4
1 2 4 8
------- test 4 ----
4 4
1 2 4 8
------- test 5 ----
20 1
1
------- test 6 ----
40 3
5 1 2
------- test 7 ----
3 10
29 50 36 43 1 2 4 8 15 22
------- test 8 ----
6 10
1 2 9 31 255 480 4 15 63 127
------- test 9 ----
8 12
1 2 4 15 9 31 63 127 255 511 1000 1999
------- test 10 ----
200 14
1 2 4 15 9 31 63 2100 3500 127 255 511 1000 1999
------- test 11 ----
200 50
1 37 87 14 137 4016 157 5383 7318 8662 7074 2821 5250 9704 8986
1375 6587 5962 7190 339 1981 9719 7012 385 7926 5159 3259 5144 7846 8854
3249 3198 8408 2784 6249 4648 6799 2757 31 4116 7771 3456 3288 3020 3159
8625 747 9745 938 10000
------- test 12 ----
200 15
1 3 14 59 265 358 979 323 846 26 433 832 7950 28 841
------- test 13 ----
200 15
1 1 1 1 1 10 10 10 10 10 100 100 100 100 100
Keep up the good work!
Thanks for your submission!
的：
-----------------------------------------------------------
/*
ID:yunleis2
PROG:stamps
LANG:C++
*/
#include<iostream>
#include<fstream>
using namespace std;
int values[50];
const unsigned int maxnum=100000;
int results[maxnum];
#define INDEX(x) ((x)%maxnum)
int main()
{
int k,n;
fstream fin("stamps.in",ios::in);
fin>>k>>n;
for(int i=0;i<n;i++)
fin>>values[i];
for(int i=0;i<maxnum;i++)
results[INDEX(i)]=-1;
results[INDEX(0)]=0;
int ptr=-1;
for(int i=0;;i++)
{
if(results[INDEX(i)]>k)
{
ptr=i;
break;
}
for(int j=0;j<n;j++)
{
if(results[INDEX(i+values[j])]==-1||((results[INDEX(i+values[j])])>(results[INDEX(i)]+1)))
results[INDEX(i+values[j])]=results[INDEX(i)]+1;
}
results[INDEX(i)]=-1;
}
if(ptr==-1)
cout<<"error"<<endl;
fstream fout("stamps.out",ios::out);
for(int i=ptr;i>=0;i--)
{
if(results[INDEX(i)]<k)
{
ptr=i+1;
break;
}
}
for(int i=ptr;;i++)
{
if(results[INDEX(i)]==-1||results[INDEX(i)]>k)
{
ptr=i-1;
break;
}
}
fout<<ptr<<endl;
// int i=0;
// for(i=ptr;i<maxnum&&results[INDEX(i]<=k;i++)
// cout<<"("<<i<<","<<results[INDEX(i]<<")"<<"\t";
//i--;
//fout<<i<<endl;
// system("pause");
}
最後更新：2017-04-02 06:51:52