SHARE
    TWEET
    Vince14

    /<> 1006 (DP circular -> linear)

    Oct 28th, 2023
    127
    0
    Never
    Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
    C++ 5.57 KB | Source Code | 0 0
    1. #include <iostream>
    2. #include <string>
    3. #include <cstring>
    4. #include <algorithm>
    5. #include <cmath>
    6. #include <vector>
    7. #include <set>
    8. #include <map>
    9. #include <stack>
    10. #include <queue>
    11. #include <deque>
    12. #include <unordered_map>
    13. #include <numeric>
    14. #include <iomanip>
    15. using namespace std;
    16. #define pii pair<int , int>
    17. #define ll long long
    18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
    19. const long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};
    20. const long long dl[2] = {1, -1};
    21. const long long MOD = 1000000007;
    22. const long long MAXN = 10005;
    24. int t;
    25. int n, w;
    26. vector<int> inside, outside;
    27. int dp[MAXN][2][2];
    29. void init(){
    30. inside.clear();
    31. outside.clear();
    32. cin >> n >> w;
    33. inside.push_back(-1);
    34. for(int x, i = 0; i < n; i++){
    35. cin >> x;
    36. inside.push_back(x);
    37. }
    38. outside.push_back(-1);
    39. for(int x, i = 0; i < n; i++){
    40. cin >> x;
    41. outside.push_back(x);
    42. }
    43. inside[0] = inside.back();
    44. outside[0] = outside.back();
    45. }
    47. int DP1(){
    48. for(int i = 0; i <= n; i++){
    49. dp[i][0][0] = 2e9;
    50. dp[i][0][1] = 2e9;
    51. dp[i][1][0] = 2e9;
    52. dp[i][1][1] = 2e9;
    53. }
    54. // idx, inside, outside
    55. dp[1][1][0] = 1;
    56. dp[1][0][1] = 1;
    57. dp[0][1][1] = 0;
    58. if(inside[1] + outside[1] <= w){
    59. dp[1][1][1] = 1;
    60. }
    61. else{
    62. dp[1][1][1] = 2;
    63. }
    64. for(int i = 2; i <= n; i++){
    65. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][1] + 1);
    66. if(inside[i] + inside[i - 1] <= w){
    67. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + 1);
    68. }
    69. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1] + 1);
    70. if(outside[i] + outside[i - 1] <= w){
    71. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0] + 1);
    72. }
    73. dp[i][1][1] = min(dp[i][1][1], min(dp[i][0][1] + 1, dp[i][1][0] + 1));
    74. if(inside[i] + outside[i] <= w){
    75. dp[i][1][1] = min(dp[i][1][1], dp[i - 1][1][1] + 1);
    76. }
    77. if(inside[i] + inside[i - 1] <= w && outside[i] + outside[i - 1] <= w){
    78. dp[i][1][1] = min(dp[i][1][1], dp[i - 2][1][1] + 2);
    79. }
    80. }
    81. return dp[n][1][1];
    82. }
    84. int DP2(){
    85. if(inside[0] + inside[1] > w){
    86. return 2e9;
    87. }
    88. for(int i = 0; i <= n; i++){
    89. dp[i][0][0] = 2e9;
    90. dp[i][0][1] = 2e9;
    91. dp[i][1][0] = 2e9;
    92. dp[i][1][1] = 2e9;
    93. }
    94. dp[1][1][0] = 1;
    95. dp[1][1][1] = 2;
    96. for(int i = 2; i <= n; i++){
    97. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][1] + 1);
    98. if(inside[i] + inside[i - 1] <= w){
    99. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + 1);
    100. }
    101. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1] + 1);
    102. if(outside[i] + outside[i - 1] <= w){
    103. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0] + 1);
    104. }
    105. dp[i][1][1] = min(dp[i][1][1], min(dp[i][0][1] + 1, dp[i][1][0] + 1));
    106. if(inside[i] + outside[i] <= w){
    107. dp[i][1][1] = min(dp[i][1][1], dp[i - 1][1][1] + 1);
    108. }
    109. if(inside[i] + inside[i - 1] <= w && outside[i] + outside[i - 1] <= w){
    110. dp[i][1][1] = min(dp[i][1][1], dp[i - 2][1][1] + 2);
    111. }
    112. }
    113. return dp[n][0][1];
    114. }
    116. int DP3(){
    117. if(outside[0] + outside[1] > w){
    118. return 2e9;
    119. }
    120. for(int i = 0; i <= n; i++){
    121. dp[i][0][0] = 2e9;
    122. dp[i][0][1] = 2e9;
    123. dp[i][1][0] = 2e9;
    124. dp[i][1][1] = 2e9;
    125. }
    126. dp[1][0][1] = 1;
    127. dp[1][1][1] = 2;
    128. for(int i = 2; i <= n; i++){
    129. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][1] + 1);
    130. if(inside[i] + inside[i - 1] <= w){
    131. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + 1);
    132. }
    133. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1] + 1);
    134. if(outside[i] + outside[i - 1] <= w){
    135. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0] + 1);
    136. }
    137. dp[i][1][1] = min(dp[i][1][1], min(dp[i][0][1] + 1, dp[i][1][0] + 1));
    138. if(inside[i] + outside[i] <= w){
    139. dp[i][1][1] = min(dp[i][1][1], dp[i - 1][1][1] + 1);
    140. }
    141. if(inside[i] + inside[i - 1] <= w && outside[i] + outside[i - 1] <= w){
    142. dp[i][1][1] = min(dp[i][1][1], dp[i - 2][1][1] + 2);
    143. }
    144. }
    145. return dp[n][1][0];
    146. }
    148. int DP4(){
    149. if(inside[0] + inside[1] > w or outside[0] + outside[1] > w){
    150. return 2e9;
    151. }
    152. for(int i = 0; i <= n; i++){
    153. dp[i][0][0] = 2e9;
    154. dp[i][0][1] = 2e9;
    155. dp[i][1][0] = 2e9;
    156. dp[i][1][1] = 2e9;
    157. }
    158. dp[1][1][1] = 2;
    159. for(int i = 2; i <= n; i++){
    160. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][1][1] + 1);
    161. if(inside[i] + inside[i - 1] <= w){
    162. dp[i][1][0] = min(dp[i][1][0], dp[i - 1][0][1] + 1);
    163. }
    164. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1] + 1);
    165. if(outside[i] + outside[i - 1] <= w){
    166. dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0] + 1);
    167. }
    168. dp[i][1][1] = min(dp[i][1][1], min(dp[i][0][1] + 1, dp[i][1][0] + 1));
    169. if(inside[i] + outside[i] <= w){
    170. dp[i][1][1] = min(dp[i][1][1], dp[i - 1][1][1] + 1);
    171. }
    172. if(inside[i] + inside[i - 1] <= w && outside[i] + outside[i - 1] <= w){
    173. dp[i][1][1] = min(dp[i][1][1], dp[i - 2][1][1] + 2);
    174. }
    175. }
    176. return dp[n - 1][1][1];
    177. }
    179. void solve(){
    180. init();
    181. if(n == 1){
    182. cout << DP1() << "\n";
    183. return;
    184. }
    185. cout << min(min(DP1(), DP2()), min(DP3(), DP4())) << "\n";
    186. }
    188. int main() {
    189. FAST;
    190. cin >> t;
    191. for(int i = 0; i < t; i++){
    192. solve();
    193. }
    194. }
    Advertisement
    Add Comment
    Please, Sign In to add comment
    Public Pastes
    We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
    Not a member of Pastebin yet?
    Sign Up, it unlocks many cool features!

    AltStyle によって変換されたページ (->オリジナル) /