fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> snake, bigthenfirst;
  6. int cache[401][401][401]; //현재 그물망 사이즈는 i번째 index, 지금 보고 있는 index, 남은 변경 가능 수
  7. const int INF = 98765432;
  8.  
  9. int space(int i, int here, int remain)
  10. {
  11. 	cout<<i<<here<<remain<<'\n';
  12. 	if(here >= snake.size()) return 0; //index out of range
  13. 	if(remain == 0 && snake[i] < snake[here]) return INF; //불가능한 노드 처리
  14.  
  15. 	int& ret = cache[i][here][remain];
  16. 	if(ret != -1) return ret;
  17.  
  18. 	ret = INF;
  19. 	if(snake[i] >= snake[here])
  20. 		ret = min(ret, space(i,here+1,remain) + snake[i] - snake[here]);
  21. 	if(remain > 0)
  22. 	{
  23. 		for(int j=0;j<snake.size();++j)
  24. 		{
  25. 			if(snake[j] >= snake[here])
  26. 			{
  27. 				ret = min(ret, space(j,here+1,remain-1) + snake[j] - snake[here]);
  28. 			}
  29. 		}
  30. 	}
  31. 	return ret;
  32. }
  33. int main()
  34. {
  35. 	cin.tie(0);
  36. 	ios::sync_with_stdio(0);
  37. 	int n, k;
  38. 	cin>>n>>k;
  39. 	snake.assign(n,0);
  40. 	for(int i=0;i<n;++i)
  41. 	{
  42. 		cin>>snake[i];
  43. 		if(snake[i] > snake[0])
  44. 			bigthenfirst.push_back(i);
  45. 	}
  46. 	memset(cache,-1,sizeof(cache));
  47. 	for(auto i : snake) cout<<i<<'\n';
  48.  
  49. 	int ret = space(0,0,k);
  50. 	for(auto i : bigthenfirst)
  51. 	{
  52. 		ret = min(ret, space(i,0,k));
  53. 	}
  54. 	for(int i=0;i<n;++i)
  55. 	{
  56. 		for(int j=0;j<n;++j)
  57. 		{
  58. 			for(int k=0;k<n;++k)
  59. 			{
  60. 				cout<<i<<j<<k<<':'<<cache[i][j][k]<<'\n';
  61. 			}
  62. 		}
  63. 	}
  64. 	cout<<ret;
  65. }
Success #stdin #stdout 0.07s 255264KB
comments (?)
stdin
copy 
6 2
7 9 8 2 3 2
stdout
copy 
7
9
8
2
3
2
002
012
121
131
141
151
161
060
160
260
360
460
560
050
060
150
160
250
260
450
460
040
050
140
150
240
250
340
440
450
540
130
140
230
240
011
120
130
111
121
120
211
120
102
112
122
132
142
152
162
061
161
261
361
461
561
051
061
060
160
260
360
460
560
151
251
261
060
160
260
360
460
560
451
461
060
160
260
360
460
560
041
051
050
150
250
450
141
241
251
050
150
250
450
341
050
150
250
450
441
451
050
150
250
450
541
050
150
250
450
131
231
241
040
140
240
340
440
540
121
011
111
211
202
212
121
011
111
211
000:-1
001:-1
002:3
003:-1
004:-1
005:-1
010:-1
011:21
012:3
013:-1
014:-1
015:-1
020:-1
021:-1
022:-1
023:-1
024:-1
025:-1
030:-1
031:-1
032:-1
033:-1
034:-1
035:-1
040:9
041:1
042:-1
043:-1
044:-1
045:-1
050:5
051:0
052:-1
053:-1
054:-1
055:-1
100:-1
101:-1
102:4
103:-1
104:-1
105:-1
110:-1
111:3
112:2
113:-1
114:-1
115:-1
120:21
121:3
122:2
123:-1
124:-1
125:-1
130:20
131:2
132:1
133:-1
134:-1
135:-1
140:13
141:1
142:0
143:-1
144:-1
145:-1
150:7
151:0
152:0
153:-1
154:-1
155:-1
200:-1
201:-1
202:4
203:-1
204:-1
205:-1
210:-1
211:21
212:3
213:-1
214:-1
215:-1
220:-1
221:-1
222:-1
223:-1
224:-1
225:-1
230:17
231:2
232:-1
233:-1
234:-1
235:-1
240:11
241:1
242:-1
243:-1
244:-1
245:-1
250:6
251:0
252:-1
253:-1
254:-1
255:-1
300:-1
301:-1
302:-1
303:-1
304:-1
305:-1
310:-1
311:-1
312:-1
313:-1
314:-1
315:-1
320:-1
321:-1
322:-1
323:-1
324:-1
325:-1
330:-1
331:-1
332:-1
333:-1
334:-1
335:-1
340:-1
341:1
342:-1
343:-1
344:-1
345:-1
350:-1
351:-1
352:-1
353:-1
354:-1
355:-1
400:-1
401:-1
402:-1
403:-1
404:-1
405:-1
410:-1
411:-1
412:-1
413:-1
414:-1
415:-1
420:-1
421:-1
422:-1
423:-1
424:-1
425:-1
430:-1
431:-1
432:-1
433:-1
434:-1
435:-1
440:1
441:0
442:-1
443:-1
444:-1
445:-1
450:1
451:0
452:-1
453:-1
454:-1
455:-1
500:-1
501:-1
502:-1
503:-1
504:-1
505:-1
510:-1
511:-1
512:-1
513:-1
514:-1
515:-1
520:-1
521:-1
522:-1
523:-1
524:-1
525:-1
530:-1
531:-1
532:-1
533:-1
534:-1
535:-1
540:-1
541:1
542:-1
543:-1
544:-1
545:-1
550:-1
551:-1
552:-1
553:-1
554:-1
555:-1
3
https://ideone.com/nDVQa4
language:
C++14 (gcc 8.3)
created:
4 years 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!