fork download
copy 
  1. /**
  2.  
  3.  *    author:  orzvanh14
  4.  
  5.  *    created: 23.12.2022 10:08:02
  6.  
  7.  *    too lazy to update time
  8.  
  9. **/
  10.  
  11. // i wants to take ioi
  12.  
  13. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  14.  
  15. #include <bits/stdc++.h>
  16.  
  17. using namespace std;
  18.  
  19. #define int long long
  20.  
  21. #define nn "\n"
  22.  
  23. #define pi pair<int, int>
  24.  
  25. #define fi first
  26.  
  27. #define se second
  28.  
  29. #define lb lower_bound
  30.  
  31. #define ub upper_bound
  32.  
  33. #define eb emplace_back
  34.  
  35. #define pb push_back
  36.  
  37. #define TASK " "
  38.  
  39. #define ms(a, x) memset(a, x, sizeof(a))
  40.  
  41. #define all(a) a.begin(), a.end()
  42.  
  43. #define All(a, n) a + 1, a + 1 + n
  44.  
  45. #define LOG 19
  46.  
  47. const int INF = 1e18;
  48.  
  49. const int mod = 1e3+7;
  50.  
  51. const int N = 305;
  52.  
  53. const int maxN = 1e5 + 5;
  54.  
  55. int MOD = 998244353;
  56.  
  57. int bit[200000];
  58.  
  59. int n;
  60.  
  61. int a[N];
  62.  
  63. int dp[N][N];
  64.  
  65. void nhap(){
  66.  
  67. 	cin >> n;
  68. 	for(int i = 1; i <= n - 1; i++){
  69. 		cin >> a[i];
  70. 	}
  71.  
  72. }
  73.  
  74. void solve(){
  75.  
  76. 	for(int i = 0; i <= n; i++){
  77. 		for(int j = 0; j <= n; j++){
  78. 			dp[i][j] = INF;
  79. 		}
  80. 	}
  81. 	dp[0][1] = 0;
  82. 	for(int i = 0; i < n; i++){
  83. 		for(int j = 1; j <= n; j++){
  84. 			if(dp[i][j] == INF) continue;
  85. 			if(i + j >= n){
  86. 				dp[n][j] = min(dp[n][j], dp[i][j]);
  87. 			}
  88. 			for(int k = i + 1; k <= min(n - 1, i + j); k++){
  89. 				dp[k][j] = min(dp[k][j], dp[i][j] + 1);
  90. 				if(j + 1 <= n){
  91. 					dp[k][j + 1] = min(dp[k][j + 1],
  92. 						dp[i][j] + a[k] + 1);
  93. 				}
  94. 			}
  95. 		}
  96. 	}
  97. 	int ans = INF;
  98. 	for(int j = 1; j <= n; j++){
  99. 		ans = min(ans, dp[n][j]);
  100. 	}
  101. 	cout << ans << nn;
  102.  
  103. }
  104.  
  105. signed main(){
  106.  
  107. 	ios_base::sync_with_stdio(0);
  108. 	cin.tie(0);
  109. 	cout.tie(0);
  110. 	nhap();
  111. 	solve();
  112. 	return (0 ^ 0);
  113. }
  114.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
8
5 1 9 1 9 9 9
stdout
copy 
5
https://ideone.com/JKGtu9
language:
C++14 (gcc 8.3)
created:
1 day 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!