注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3699]GAL的数组  

2014-07-20 21:16:14|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

  给出3*n个数xi,要求构造三个长度为n的序列ai,bi,ci,使得满足下列条件:

    1到3*n的每个数都在三个序列中的某个出现一次且仅一次;

    S=sum((x[ai]-x[bi])*x[ci])最大。

  输出最大的S。多组数据。

Input Format

  第一行包含两个数T和n,T是数据组数,n如题目描述。

  接下来T行,每行包含3*n个数,表示xi。

Output Format

  输出包含T行,每行输出最大的S。

Sample Input

1 2
4 1 8 2 0 5

Sample Output

46

Hint

  对于1<=n<=10,有不超过1000组数据;

  对于11<=n<=15,又不超过100组数据;

  对于16<=n<=20,有不超过10组数据;

  对于21<=n<=25,仅有1组数据。

  所有xi<=1000。

 

Solution

  首先先Orz yff,怎么想到dfs的。。。标解是状压DP,还是卡时过的,不知比暴力慢到哪里去了。

  1. 当a>=c>=b时(a-b)*c的值最大。推一推就出来了。

  2. 将读入的3*n个数从小到大排序,x1~xn一定分别在每组中,且一定是每组的b

  3. 将n个三元组(ai,bi,ci)按照ci从小到大排序。为了使Σ( a[i] - b[i] ) * c[i]最大化,根据排序不等式可以得a1<=a2<=a3<=…<=an,b1>=b2>=…>=bn。所以b1=xn,b2=xn-1…bn=x1。

  4. 最优性剪枝:两个三元组(ai,bi,ci)与(aj,bj,cj)为最终答案,当且仅当

    (ai - bi) * ci + (aj - bj) * cj > (ai - bi) * aj + (ci - bj) * cj

    即(ci - aj) (ai - bi - cj) > 0

  然后就dfs吧= =

#include<cstdio>
#include<cstring>
#include<algorithm>
int T,n,a[30],c[30],t[100],ans,now;bool vis[100];
bool check(int x)
{
for(int i=1;i<x;i++)
{
if(c[i]>a[x]&&a[i]-t[3*n-i+1]<c[x])return 0;
if(c[i]<a[x]&&a[i]-t[3*n-i+1]>c[x])return 0;
}
return 1;
}
void dfs(int xa,int tc)
{
if(xa==n+1)
{
if(ans<now)ans=now;
return;
}
for(int i=xa;i<=2*n;i++)
if(!vis[i])
{
vis[i]=1,a[xa]=t[i];
for(int j=std::max(i,tc)+1;j<=2*n;j++)
if(!vis[j])
{
vis[j]=1,c[xa]=t[j],
now+=(a[xa]-t[3*n-xa+1])*c[xa];
if(now*n>ans*xa&&check(xa))dfs(xa+1,j);
now-=(a[xa]-t[3*n-xa+1])*c[xa],vis[j]=0;
}
vis[i]=0;break;
}
}
bool cmp(int i,int j){return i>j;}
int main()
{
for(scanf("%d%d",&T,&n);T;T--)
{
for(int i=1;i<=3*n;i++)scanf("%d",&t[i]);
std::sort(t+1,t+1+3*n,cmp);ans=0;
dfs(1,0);printf("%d\n",ans);
}
}

  评论这张
 
阅读(46)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018