QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358654#6306. Chase GameLast_FlameTL 0ms0kbC++142.3kb2024-03-19 22:06:562024-03-19 22:06:56

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 22:06:56]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-19 22:06:56]
  • 提交

answer

/*
考虑建模,将合并操作当作新建一个节点,作为合并的两摞书的父节点,相当于合并后的一摞书 
考虑这样建出的二叉树可以唯一的确定一种合并方案,考虑这种合并方案的贡献怎么计算 
考虑每个叶子结点代表最开始的一本书,重量值的贡献就是每本书的 W 乘上该节点的深度 
考虑磨损值怎么计算,考虑进行长链剖分,因为对于一个节点,其磨损值一定是取决于其子树中最深的深度,因为合并时我们肯定选小磨损值贡献 
考虑进行长链剖分后,考虑每条链只会做 2^(n-1)-1 的贡献 
我们考虑设计状态 f(i,j) 表示已经钦定了 i 个节点为叶子,当前层还有 j 个节点不是叶子,n<i+j 的状态是不合法的,可以减掉 
考虑转移,可以结束当前层的决策,f(i,2*j)=f(i,j)+sigma(w(k))(k>i) 
可以钦定一个叶子,f(i+1,j-1)=f(i,j)+lowbit(j)/2 
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mn=10086;
int T,n,w[mn];
int n2[30],lb[mn];
ll sumw[mn],dp[2][mn];
int now,to;
ll ans;

int read(){
	int x=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	} 
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*w;
} 

void ready(){
	n2[0]=1;
	for(int i=1;i<=20;i++) n2[i]=n2[i-1]<<1;
	for(int i=0;i<=13;i++){
		for(int j=n2[i];j<=1e4;j+=n2[i+1]) lb[j]=n2[i];
	}
	return;
}

void clear(){
	for(int i=0;i<=n;i++) dp[now][i]=1e18;
	return;
}

int main(){
	T=read();
	
	ready();
	
	while(T--){
		n=read();
		for(int i=1;i<=n;i++) w[i]=read();
		
		sort(w+1,w+n+1);
		sumw[0]=0;
		for(int i=1;i<=n;i++) sumw[i]=sumw[i-1]+w[i];
		
		for(int i=0;i<=1;i++) for(int j=0;i+j<=n;j++) dp[i][j]=1e18;
		dp[0][1]=0;
		now=1,to=0;
		for(int i=0;i<n;i++){
			now=(now+1)%2,to=(now+1)%2;
			for(int j=1;i+j<=n;j++){
				if((j<<1)<=n) dp[now][j<<1]=min(dp[now][j<<1],dp[now][j]+sumw[n-i]);
				dp[to][j-1]=min(dp[to][j-1],dp[now][j]+lb[j-1]);
			}
			clear();
		}
		
		ans=dp[to][0]-(n-1);
		
		cout<<ans<<endl;
	}
	
	return 0;
}
/*
5
6
1 1 4 5 1 4
6
10 10 40 50 10 40
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
1 3 15 105 945 27455185
6
1 2 3 4 5 6

1
4
1 1 1 1
*/

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

21
25

result: