fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11. 	vector<int> a(n + 1);
  12.  
  13. 	for(int i = 1; i <= n; i++){
  14. 		cin >> a[i];
  15. 	}
  16.  
  17. 	vector<vector<int>> wrong(n + 1, vector<int>(n + 1, 0));
  18.  
  19. 	for(int i = 1; i <= n; i++){
  20. 		int x = 1;
  21. 		int cnt = 0;
  22. 		for(int j = i + 2; j <= n; j++){
  23. 			if(a[j - 1] != x){
  24. 				cnt++;
  25. 			}
  26. 			x++;
  27. 			wrong[i][j] = cnt;
  28.  
  29. 		}
  30.  
  31. 	}
  32.  
  33.  
  34. 	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 10));
  35. 	dp[0][0] = 0;
  36. 	vector<int> ans(n + 1, n);
  37. 	for(int j = 1; j <= n; j++){
  38. 		for(int k = 2 - (j == 1); k <= j; k++){
  39. 			for(int l = j - 1; l >= 0; l--){
  40. 				dp[j][k] = min(dp[j][k], dp[l][k - 1] + wrong[l][j] + (a[j] != 0));
  41. 			}
  42. 			int x = 1;
  43. 			int cnt = 0;
  44. 			for(int l = j + 1; l <= n; l++){
  45. 				if(a[l] != x)cnt++;
  46. 				x++;
  47. 			}
  48. 			ans[k] = min(ans[k], dp[j][k] + cnt);
  49. 		}
  50. 	}
  51. 	for(int i = 1; i <= n;i++){
  52. 		cout << ans[i] << "\n";
  53. 	}
  54.  
  55.  
  56. }
  57.  
  58. int main(){
  59. 	ios_base::sync_with_stdio(false);
  60. 	cin.tie(nullptr);
  61.  
  62. 	freopen("taming.in", "r", stdin);
  63. 	freopen("taming.out", "w", stdout);
  64. 	int t = 1;
  65. 	// cin >> t;
  66.  
  67. 	for(int i = 1; i <= t; i++){
  68. 		solve();
  69. 	}
  70. 	return 0;
  71. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
1 1 2 0 0 1
stdout
copy 
Standard output is empty
https://ideone.com/s4nYtN
language:
C++14 (gcc 8.3)
created:
5 hours 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!