fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 2e9;   
  8. const ll LINF = 1e18; 
  9. const int N = 6e4 + 5;  
  10.  
  11. int n;  
  12. ll t[N], r[N]; 
  13. ll dp[N];  
  14.  
  15. ll memo[N];  
  16.  
  17. ll f(int n) {
  18. 	if (n == 0) return 0; 
  19. 	if (n == 1) return t[1];   
  20.  
  21. 	ll& ans = memo[n];  
  22. 	if (ans != -1) return ans;   
  23.  
  24. 	ans = min(t[n] + f(n - 1), r[n - 1] + f(n - 2)); 
  25.  
  26. 	return ans;  
  27. }
  28.  
  29. int main() {
  30. 	ios::sync_with_stdio(0); cin.tie(0);  	
  31. 	int n;  
  32. 	cin >> n;   
  33.  
  34. 	for (int i = 1; i <= n; i++) cin >> t[i];  
  35. 	for (int i = 1; i <= n - 1; i++) cin >> r[i]; 
  36.  
  37. 	// // get về  
  38. 	// {
  39. 	// 	dp[1] = t[1];   
  40. 	// 	dp[2] = min(dp[1] + t[2], r[1]); 
  41. 	// 	for (int i = 3; i <= n; i++) {
  42. 	// 		// xét trường hợp người thứ i tự mua và nhờ mua hộ
  43. 	// 		dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + r[i - 1]); 
  44. 	// 	}
  45.  
  46. 	// 	cout << dp[n] << '\n'; 
  47. 	// }
  48.  
  49. 	// // update lên 
  50. 	// {	
  51. 	// 	for (int i = 0; i <= n; i++) dp[i] = INF;  
  52. 	// 	dp[0] = 0;  
  53. 	// 	for (int i = 0; i < n; i++) {
  54. 	// 		// xét trường hợp người thứ i + 1 tự mua hoặc người thứ i + 1 mua hộ i + 2
  55. 	// 		dp[i + 1] = min(dp[i + 1], dp[i] + t[i + 1]);   
  56. 	// 		dp[i + 2] = min(dp[i + 2], dp[i] + r[i + 1]); 
  57. 	// 	}
  58.  
  59. 	// 	cout << dp[n] << '\n'; 
  60. 	// }
  61.  
  62. 	// đệ quy 
  63. 	{
  64. 		memset(memo, -1, sizeof memo);  
  65. 		cout << f(n) << '\n'; 
  66. 	}
  67. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
5
2 5 7 8 4
4 9 10 10
stdout
copy 
18
https://ideone.com/5hHZy4
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!