UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190089#3324. 树苗(tree)Harry2718210043ms1248kbC++11684b2023-10-05 09:54:592023-10-05 12:41:06

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[25],b[25],ans=1e18;
signed main()
{
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<(1<<n);i++)
	{
		if(__builtin_popcount(i)!=m||i%2==0)continue;
		for(int j=0;j<n;j++)b[j]=a[j];
		int lst=-1,val=0;
		for(int j=0;j<n;j++)
		{
			if(i&(1<<j))
			{
				if(lst!=-1&&b[j]<=b[lst])val+=b[lst]-b[j]+1,b[j]=b[lst]+1;
				lst=j;
			}
			else 
			{
				if(lst!=-1&&b[j]>b[lst])val+=b[j]-b[lst],b[lst]=b[j];
			}
		}
		ans=min(ans,val);
	}
	cout<<ans;
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 2ms
memory: 1248kb

input:

20 20
941875906 3822781 449168967 380996194 74552217 351678383 338576429 283097025 621089816 1234573...

output:

9681131585

result:

ok single line: '9681131585'

Test #2:

score: 10
Accepted
time: 5ms
memory: 1240kb

input:

20 20
10527421 20948275 30261754 40147397 50420704 60722213 70623948 80280790 90554478 100845904 110...

output:

0

result:

ok single line: '0'

Test #3:

score: 10
Accepted
time: 5ms
memory: 1244kb

input:

20 20
375647377 694803432 405638673 452074257 316494968 812425781 410220501 947545545 44110880 85091...

output:

5689322908

result:

ok single line: '5689322908'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

5 1
3 1 1 5 5

output:

2

result:

ok single line: '2'

Test #5:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

5 3
2 2 5 1 3

output:

1

result:

ok single line: '1'

Test #6:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

5 2
1 3 5 4 3

output:

2

result:

ok single line: '2'

Test #7:

score: 10
Accepted
time: 9ms
memory: 1248kb

input:

20 8
871929662 439792376 687409670 637699165 203379564 510322553 505657251 897767419 304747573 85858...

output:

736612128

result:

ok single line: '736612128'

Test #8:

score: 10
Accepted
time: 7ms
memory: 1244kb

input:

20 14
10921365 20321584 30579098 40050141 50403179 60323927 70745971 80704811 90854918 100515713 110...

output:

56961014

result:

ok single line: '56961014'

Test #9:

score: 10
Accepted
time: 6ms
memory: 1248kb

input:

20 5
914351454 702197249 215474099 579049794 227028026 493073867 90377697 379425068 420699945 871931...

output:

273231451

result:

ok single line: '273231451'

Test #10:

score: 10
Accepted
time: 9ms
memory: 1244kb

input:

20 8
10866256 20629926 30221774 40863655 50628050 60358417 70313111 80777586 90253514 100514012 1100...

output:

116217608

result:

ok single line: '116217608'

Extra Test:

score: 0
Extra Test Passed