[FJOI2014] 石子合并问题

2014年3月31日6,6302

问题描述

有n堆石子，每堆1个，要合并成一堆，规定每次可以任意选两堆合并成新的一堆，两堆中较少的石子数记为该次合并的得分。

输入n

输出最大得分

样例输入 7

样例输出 9

O（n）做法

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[20001];
int main()
{
    scanf("%d",&n);
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
       if(i&1)
       	   f[i]=f[i>>1]+f[(i>>1)+1];
       else f[i]=(f[i>>1]<<1);
       f[i]+=(i>>1);
    }
    printf("%d",f[n]);
	return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int n,f[20001];

int main()

{

scanf("%d",&n);

f[1]=0;

for(int i=2;i<=n;i++)

{

if(i&1)

f[i]=f[i>>1]+f[(i>>1)+1];

else f[i]=(f[i>>1]<<1);

f[i]+=(i>>1);

}

printf("%d",f[n]);

return 0;

}

O（nlogn）堆

ndsf神犇秒杀

#include<cstdio>  
#include<queue> 
long long n,ans=0;  
using namespace std;  
int main()  
{  
    priority_queue<long long,vector<long long>,greater<long long> > q;  
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)q.push(1); 
    for(int i=1;i<=n-1;i++)  
    {  
        int x=q.top();q.pop(); 
        int y=q.top();q.pop(); 
        ans+=min(x,y);  
        q.push(x+y);  
    }  
    printf("%d",ans);  
    return 0;  
}