B题有没有不用贪心用背包做的大佬的题解啊
看不懂大佬们用贪心做的，想看看有没有dp。。。
2019-01-23 16:29 华东交通大学
关注
全部评论
Sqssq
Java
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int t[100005]={0};
int main()
{
int n;
int i;
scanf("%d",&n);
int a2=0,a0=0,a4=0;
int k;
for(i=1;i<=n;i++){
scanf("%d",&k);
if(k==2){
a2++;
}
else if(k==0){
a0++;
}
else if(k==4){
a4++;
}
}
t[0]=0;
for(i=1;i<=n;i++){
if(a4>0){
t[i]=4;
a4--;
if(a0>0){
t[i+1]=0;
i++;
a0--;
}
else if(a2>0){
t[i+1]=2;
i++;
a2--;
}
}
else if(a2>0){
t[i]=2;
a2--;
if(a0>0){
t[i+1]=0;
i++;
a0--;
}
}
else{
t[i]=0;
}
}
long long int sum=0;
for(i=1;i<=n;i++){
sum+=pow(t[i]-t[i-1],2);
}
printf("%lld",sum);
return 0;
}
送花
回复
分享
相关推荐
投递游卡等公司7个岗位 >