QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358654 | #6306. Chase Game | Last_Flame | TL | 0ms | 0kb | C++14 | 2.3kb | 2024-03-19 22:06:56 | 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