Differences From Artifact [feb5fdb1e50b8e31]:
- File
lib/typical/dp.cpp
- 2011-12-29 06:57:30 - part of checkin [3d2bcff745] on branch trunk - 528 (user: kinaba) [annotate]
To Artifact [3e3b37ddf9926aec]:
- File
lib/typical/dp.cpp
- 2013-12-15 07:31:02 - part of checkin [ad9e7615bd] on branch trunk - 256MB (user: kinaba) [annotate]
1 // Tested: SRM 454 Lv2 1 // Tested: SRM 454 Lv2
2 template<typename T> 2 template<typename T>
3 struct DP2 3 struct DP2
4 { 4 {
5 const int N1, N2; 5 const int N1, N2;
6 vector<T> data; 6 vector<T> data;
7 DP2(int N1, int N2, const T& t = T()) 7 DP2(int N1, int N2, const T& t = T())
8 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< | 8 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<
9 T& operator()(int i1, int i2) 9 T& operator()(int i1, int i2)
10 { return data[ (i1*N2)+i2 ]; } 10 { return data[ (i1*N2)+i2 ]; }
11 void swap(DP2& rhs) 11 void swap(DP2& rhs)
12 { data.swap(rhs.data); } 12 { data.swap(rhs.data); }
13 }; 13 };
14 14
15 // Tested: Codeforces #13 C, SRM 528 Lv2 15 // Tested: Codeforces #13 C, SRM 528 Lv2
16 template<typename T> 16 template<typename T>
17 struct DP2x 17 struct DP2x
18 { 18 {
19 const int N1, N2; 19 const int N1, N2;
20 vector<T> data; 20 vector<T> data;
21 DP2x(int, int N2, const T& t = T()) 21 DP2x(int, int N2, const T& t = T())
22 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<( | 22 : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(
23 T& operator()(int i1, int i2) 23 T& operator()(int i1, int i2)
24 { i1&=1; return data[ (i1*N2)+i2 ]; } 24 { i1&=1; return data[ (i1*N2)+i2 ]; }
25 void swap(DP2x& rhs) 25 void swap(DP2x& rhs)
26 { data.swap(rhs.data); } 26 { data.swap(rhs.data); }
27 }; 27 };
28 28
29 // Tested: SRM 452 Lv3 29 // Tested: SRM 452 Lv3
30 template<typename T> 30 template<typename T>
31 struct DP3 31 struct DP3
32 { 32 {
33 int N1, N2, N3; 33 int N1, N2, N3;
34 vector<T> data; 34 vector<T> data;
35 DP3(int N1, int N2, int N3, const T& t = T()) 35 DP3(int N1, int N2, int N3, const T& t = T())
36 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() | 36 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()
37 T& operator()(int i1, int i2, int i3) 37 T& operator()(int i1, int i2, int i3)
38 { return data[ ((i1*N2)+i2)*N3+i3 ]; } 38 { return data[ ((i1*N2)+i2)*N3+i3 ]; }
39 void swap(DP3& rhs) 39 void swap(DP3& rhs)
40 { data.swap(rhs.data); } 40 { data.swap(rhs.data); }
41 }; 41 };
42 42
43 // Tested: SRM 468 Lv2 43 // Tested: SRM 468 Lv2
44 template<typename T> 44 template<typename T>
45 struct DP3x 45 struct DP3x
46 { 46 {
47 int N1, N2, N3; 47 int N1, N2, N3;
48 vector<T> data; 48 vector<T> data;
49 DP3x(int, int N2, int N3, const T& t = T()) 49 DP3x(int, int N2, int N3, const T& t = T())
50 : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()* | 50 : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*
51 T& operator()(int i1, int i2, int i3) 51 T& operator()(int i1, int i2, int i3)
52 { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } 52 { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
53 void swap(DP3x& rhs) 53 void swap(DP3x& rhs)
54 { data.swap(rhs.data); } 54 { data.swap(rhs.data); }
55 }; 55 };
56 56
57 // Tested: SRM 520 Lv2 57 // Tested: SRM 520 Lv2
58 template<typename T> 58 template<typename T>
59 struct DP4 59 struct DP4
60 { 60 {
61 int N1, N2, N3, N4; 61 int N1, N2, N3, N4;
62 vector<T> data; 62 vector<T> data;
63 DP4(int N1, int N2, int N3, int N4, const T& t = T()) 63 DP4(int N1, int N2, int N3, int N4, const T& t = T())
64 : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert( | 64 : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(
65 T& operator()(int i1, int i2, int i3, int i4) 65 T& operator()(int i1, int i2, int i3, int i4)
66 { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } 66 { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
67 void swap(DP4& rhs) 67 void swap(DP4& rhs)
68 { data.swap(rhs.data); } 68 { data.swap(rhs.data); }
69 }; 69 };
70 70
71 // Not Tested 71 // Not Tested
72 template<typename T> 72 template<typename T>
73 struct DP4x 73 struct DP4x
74 { 74 {
75 int N1, N2, N3, N4; 75 int N1, N2, N3, N4;
76 vector<T> data; 76 vector<T> data;
77 DP4x(int, int N2, int N3, int N4, const T& t = T()) 77 DP4x(int, int N2, int N3, int N4, const T& t = T())
78 : N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(d | 78 : N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(d
79 T& operator()(int i1, int i2, int i3, int i4) 79 T& operator()(int i1, int i2, int i3, int i4)
80 { i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } 80 { i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
81 void swap(DP4x& rhs) 81 void swap(DP4x& rhs)
82 { data.swap(rhs.data); } 82 { data.swap(rhs.data); }
83 }; 83 };
84 84
85 85
................................................................................................................................................................................
86 // Tested: SRM 351 Lv2 86 // Tested: SRM 351 Lv2
87 template<typename T> 87 template<typename T>
88 struct DP5 88 struct DP5
89 { 89 {
90 int N1, N2, N3, N4, N5; 90 int N1, N2, N3, N4, N5;
91 vector<T> data; 91 vector<T> data;
92 DP5(int N1, int N2, int N3, int N4, int N5, const T& t = T()) 92 DP5(int N1, int N2, int N3, int N4, int N5, const T& t = T())
93 : N1(N1), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t | 93 : N1(N1), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t
94 T& operator()(int i1, int i2, int i3, int i4, int i5) 94 T& operator()(int i1, int i2, int i3, int i4, int i5)
95 { return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; } 95 { return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; }
96 void swap(DP5& rhs) 96 void swap(DP5& rhs)
97 { data.swap(rhs.data); } 97 { data.swap(rhs.data); }
98 }; 98 };
99 99
100 // Not Tested 100 // Not Tested
101 template<typename T> 101 template<typename T>
102 struct DP5x 102 struct DP5x
103 { 103 {
104 int N1, N2, N3, N4, N5; 104 int N1, N2, N3, N4, N5;
105 vector<T> data; 105 vector<T> data;
106 DP5x(int, int N2, int N3, int N4, int N5, const T& t = T()) 106 DP5x(int, int N2, int N3, int N4, int N5, const T& t = T())
107 : N1(2), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t) | 107 : N1(2), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t)
108 T& operator()(int i1, int i2, int i3, int i4, int i5) 108 T& operator()(int i1, int i2, int i3, int i4, int i5)
109 { i1&=1; return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; } 109 { i1&=1; return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; }
110 void swap(DP5x& rhs) 110 void swap(DP5x& rhs)
111 { data.swap(rhs.data); } 111 { data.swap(rhs.data); }
112 }; 112 };