fork download 
  1. #define CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. using namespace std;
  4. int require;
  5. int target[101];
  6. int owned[101];
  7. int n;
  8. int m;
  9. int solinhkientronggoi[101];
  10. int linhkiengoikhuyenmai[101][101];
  11. int pricegoikhuyenmai[101];
  12. int giamuale[101];
  13.  
  14. int t;
  15. int mint = 100000;
  16. int remaining() {
  17. 	int cost = 0;
  18. 	for (int i = 1; i <= require; i++) {
  19. 		if (owned[target[i]] == 0) {
  20. 			cost += giamuale[target[i]];
  21. 		}
  22. 	}
  23. 	return cost;
  24. }
  25. bool done() {
  26. 	for (int i = 1; i <= require; i++) {
  27. 		if (owned[target[i]] == 0)return false;
  28.  
  29. 	}
  30. 	return true;
  31. }
  32. void addpack(int k,int a) {
  33. 	for (int i = 1; i <= solinhkientronggoi[k]; i++) {
  34. 		owned[linhkiengoikhuyenmai[k][i]] += a;
  35. 	}
  36. }
  37.  
  38. void backtrack(int k, int cur) {
  39.  
  40. 	if (k == m + 1) {
  41. 		if (mint > cur +remaining() ) {
  42. 			mint = cur + remaining();
  43. 		}
  44. 		return;
  45. 	}
  46. 	if (done()) {
  47. 		mint = cur;
  48. 		return;
  49. 	}
  50. 	if (cur > mint)	return; //dieu kien cat nhanh
  51. 	for (int i = 0; i < 2; i++) {
  52. 		if (i == 0) {
  53. 			backtrack(k + 1, cur);
  54. 		}
  55. 		else if (i == 1) {
  56. 			addpack(k, 1);
  57. 				backtrack(k + 1, cur + pricegoikhuyenmai[k]);
  58. 				addpack	(k, -1);
  59.  
  60. 		}
  61. 	}
  62.  
  63. }
  64.  
  65.  
  66. int main() {
  67.  
  68. 	cin >> t;
  69. 	for (int tc = 1; tc <= t; tc++) {
  70. 		cin >> n;
  71. 		for (int i = 1; i <=n; i++) {
  72. 			cin>>giamuale[i];
  73. 			}
  74. 		cin >> m;
  75. 		for (int i = 1; i <= m; i++) {
  76. 			cin >> pricegoikhuyenmai[i];
  77. 			cin >> solinhkientronggoi[i];
  78. 			for (int p = 1; p <= solinhkientronggoi[i]; p++) {
  79. 				cin >> linhkiengoikhuyenmai[i][p];
  80. 			}
  81. 		}
  82. 		for (int i = 1; i <= 100; i++) {
  83. 			owned[i] = 0;
  84. 		}
  85. 		cin >> require;
  86. 		for (int i = 0; i < require; i++) {
  87. 			cin >> target[i];
  88. 		}
  89. 		mint = 100000;
  90. 		backtrack(1, 0);
  91. 		cout << mint << endl;
  92.  
  93. 	}
  94. 	return 0;
  95. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/bvW54p
10
5
2 3 4 5 6
2
6 3 1 2 3
7 2 3 5
3
1 4 5
4
5 5 5 5
1
8 4 1 2 3 4
4
1 2 3 4
5
10 10 10 10 10
2
9 2 1 2
9 3 3 4 5
5
1 2 3 4 5
4
1 100 100 100
1
50 3 2 3 4
2
1 2
6
2 2 100 100 100 100
2
3 3 1 2 3
150 4 3 4 5 6
4
1 2 3 4
3
100 1 1
1
2 2 1 2
1
1
3
3 4 5
0
2
2 3
5
4 4 4 4 4
3
5 2 1 2
5 2 3 4
3 1 5
3
1 3 5
4
6 6 6 6
3
5 2 1 2
5 2 2 3
5 2 3 4
4
1 2 3 4
6
5 5 5 5 5 5
3
7 3 1 2 3
4 2 3 4
6 2 5 6
4
1 3 4 5
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!