Created
March 20, 2016 12:00
-
-
Save zsh-89/93b80e0a4e229a998ab2 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <map> | |
| using namespace std; | |
| class TestData | |
| { | |
| public: | |
| int N; // 箱子个数 | |
| vector<int> m; // 自重 | |
| vector<int> M; // 承重 | |
| void print() | |
| { | |
| printf("N = %d\n", N); | |
| printf("m[] = "); | |
| for (int i = 0; i < N; ++i) | |
| printf("%d ", m[i]); | |
| putchar('\n'); | |
| printf("M[] = "); | |
| for (int i = 0; i < N; ++i) | |
| printf("%d ", M[i]); | |
| putchar('\n'); | |
| } | |
| }; | |
| TestData genTestData() | |
| { | |
| TestData data; | |
| int N = rand() % 1000; | |
| data.N = N; | |
| data.m.resize(N); | |
| data.M.resize(N); | |
| for (int i = 0; i < N; ++i) { | |
| data.m[i] = rand() % 3000; | |
| data.M[i] = rand() % 3000; | |
| } | |
| return data; | |
| } | |
| class MC | |
| { | |
| public: | |
| MC(const TestData &_data) | |
| { | |
| data = _data; | |
| f.resize(F_SIZE); | |
| } | |
| int solve() | |
| { | |
| for (int i = 0; i < F_SIZE; ++i) { | |
| f[i] = 0; | |
| } | |
| for (int i = 0; i < data.N; ++i) { | |
| for (int j = 0; j <= data.M[i]; ++j) { | |
| int pos = j + data.m[i]; | |
| f[pos] = max(f[pos], f[j]+1); | |
| } | |
| } | |
| int maxima = 0; | |
| for (int i = 0; i < F_SIZE; ++i) | |
| maxima = max(maxima, f[i]); | |
| return maxima; | |
| } | |
| static const int F_SIZE = 6001; | |
| TestData data; | |
| vector<int> f; | |
| }; | |
| class ME | |
| { | |
| public: | |
| ME(const TestData &_data) | |
| { | |
| data = _data; | |
| } | |
| int solve() | |
| { | |
| int maxima = 0; | |
| for (int i = 0; i < data.N; ++i) { | |
| maxima = max(maxima, recur(INT_MAX, i)); | |
| } | |
| return maxima; | |
| } | |
| private: | |
| int recur(int W, int i) | |
| { | |
| auto iter = f.find(pair<int, int>(W, i)); | |
| if (iter != f.end()) | |
| return iter->second; | |
| if (W < data.m[i]) { | |
| f.insert(make_pair(pair<int, int>(W, i), 0)); | |
| return 0; | |
| } | |
| if (W == data.m[i] || (W >= data.m[i] && i == data.N-1)) { | |
| f.insert(make_pair(pair<int, int>(W, i), 1)); | |
| return 1; | |
| } | |
| if (W > data.m[i]) { | |
| int next_W = min(data.M[i], W-data.m[i]); | |
| int maxima = 0; | |
| for (int k = i + 1; k < data.N; ++k) { | |
| int val = recur(next_W, k); | |
| maxima = max(maxima, val); | |
| } | |
| f.insert(make_pair(pair<int, int>(W, i), maxima+1)); | |
| return maxima+1; | |
| } | |
| throw runtime_error("Impossible to reach here"); | |
| } | |
| TestData data; | |
| map<pair<int, int>, int> f; | |
| }; | |
| int main() | |
| { | |
| TestData d1 = genTestData(); | |
| d1.print(); | |
| MC mc1(d1); | |
| printf("%d\n", mc1.solve()); | |
| ME me1(d1); | |
| printf("%d\n", me1.solve()); | |
| getchar(); | |
| return 0; | |
| } | |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
N个大小相同的纸箱，分别编号1～N，N取值范围[1, 1000]，每个纸箱的自重和承重能力各异，取值范围均为[1, 3000]，现在把这些纸箱按编号从小到大、一个一个地竖直堆叠起来（编号小的在下方，编号大的在上方，可以选择放置或者不放某个箱子），问最多可以堆叠多少个。