fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. pair<long long, int> solve(int v[], int sz, int slope) {
  5.  
  6. 	// menghitung DP
  7. 	long long dp[sz+1];
  8. 	dp[0]=0;
  9. 	dp[1]=min(0,v[1]-slope);
  10. 	for(int temp=2;temp<sz;temp++)	dp[temp]=min(dp[temp-1],dp[temp-2]+v[temp]-slope);
  11.  
  12. 	// backtracking untuk mencari tahu minimum bilangan yang diambil
  13. 	long long opt=dp[sz-1];
  14. 	int pos=sz-1,cnt=0;
  15. 	while(pos>0)
  16. 	{
  17. 		if(dp[pos]==dp[pos-1])	pos--;
  18. 		else	pos-=2,cnt++;
  19. 	}
  20.  
  21. 	return {opt, cnt};
  22. }
  23. int main()
  24. {
  25. 	ios_base::sync_with_stdio(false); cin.tie(0);
  26. 	int tc;
  27. 	cin>>tc;
  28. 	while(tc--) {
  29. 		int n,k;
  30. 		cin>>n>>k;
  31. 		int a[n],temp;
  32. 		int v[n];
  33. 		v[0]=0;
  34. 		for(temp=0;temp<n;temp++) {
  35. 			cin>>a[temp];
  36. 			if(temp>0)	v[temp]=(a[temp]-a[temp-1]);
  37. 		}
  38. 		int left=0,right=1000000000,mid;
  39. 		long long gval,slope;
  40. 		int sz=n;
  41. 		while(left<=right) {
  42. 			mid=(left+right)/2;
  43.  
  44. 			// mencari G optimal dan banyaknya bilangan minimum
  45. 			pair<long long, int> ins = solve(v, sz, mid);
  46. 			long long opt=ins.first;
  47. 			int cnt=ins.second;
  48.  
  49. 			if(cnt<=k) {
  50. 				slope=mid;
  51. 				gval=opt;
  52. 				left=mid+1;
  53. 			}
  54.  
  55. 			else	right=mid-1;
  56. 		}
  57. 		cout<<gval+k*slope<<"\n";
  58. 	}
  59.  
  60. }
  61.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
1
5 2
1
3
4
6
12
stdout
copy 
4
https://ideone.com/24fLTJ
language:
C++14 (gcc 8.3)
created:
5 years 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!