USACO Section 3.1: Stamps
9424 ワード
この問題は最初にdfs(注釈部分)を用いたが,TLE,後にDP法を考え,f[i]=f[j]+f[i-j],j=1,2...i/2、それともTLE、ネット上で他の人のコードを探して、自分の状態方程式に問題があることを発見して、f[i]=f[i-stamp[j]+1で、j=1であるべきです...N.これによりjが1からNになると複雑度が大幅に低下する.
1 /*
2 ID: yingzho1
3 LANG: C++
4 TASK: stamps
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16 #include <cmath>
17 #include <list>
18 #include <cstdio>
19 #include <cstdlib>
20
21 using namespace std;
22
23 ifstream fin("stamps.in");
24 ofstream fout("stamps.out");
25
26 const int inf = 100000000;
27
28 int K, N;
29
30 /*bool check(int cur, vector<int> &stamp, int total, int dep) {
31 if (cur < 0 || total < 0) return false;
32 if (cur == 0) return true;
33 for (int i = dep; i < stamp.size(); i++) {
34 if (check(cur-stamp[i], stamp, total-1, i)) return true;
35 }
36 return false;
37 }
38
39 bool cmp(const int a, const int b) {return a > b;}*/
40
41 int main()
42 {
43 fin >> K >> N;
44 vector<int> stamp(N);
45 set<int> S;
46 for (int i = 0; i < N; i++) {
47 fin >> stamp[i];
48 S.insert(stamp[i]);
49 }
50 // sort(stamp.begin(), stamp.end(), cmp);
51 /* if (stamp[stamp.size()-1] != 1) {
52 fout << 0 << endl;
53 return 0;
54 }*/
55 vector<int> f(1);
56 int cur = 1;
57 while (cur) {
58 //cout << cur << endl;
59 if (S.count(cur)) f.push_back(1);
60 else {
61 int tmp = inf;
62 //for (int i = 1; i <= cur/2; i++) tmp = min(tmp, f[i]+f[cur-i]);
63 for (int i = 0; i < N; i++) {
64 if (cur > stamp[i]) tmp = min(tmp, f[cur-stamp[i]]+1);
65 }
66 if (tmp > K) break;
67 f.push_back(tmp);
68 }
69 cur++;
70 }
71 fout << cur-1 << endl;
72
73
74 /*int cur = 2;
75 while (check(cur, stamp, K, 0)) {
76 //cout << cur << endl;
77 cur++;
78 }
79 fout << cur-1 << endl;*/
80
81 return 0;
82 }