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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

sgu366 dp+优化  

2012-10-08 20:41:59|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
优化后的dp
之前由于负数的缘故,怒开map+set+stack+ector
于是果断超了
只得删了重写
orz丽洁的强力优化(相同差值的有用的不超过k个)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int INF=1000000000;
const int MAX=60000+10;
const int MAXA=103;
const int MAXB=2004;
const int MAXC=32;

int n,k,a[MAX],b[MAX];

struct number
{
int x,y,num;
number(){}
number(int a,int b,int c)
{
x=a;y=b;num=c;
}
}p[MAX];

int cmp(const number& a,const number& b)
{
if(a.x!=b.x)return a.x<b.x;
else return a.y>b.y;
}

int f[MAXA][MAXB][MAXC],come[MAXA][MAXB][MAXC];
int first[MAXA],last[MAXA],sum[MAX];
int ansq[MAX];

void update(int& a,int b,int& c,int d)
{
if(b>a)
{
a=b;
c=d;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j,l,o;
scanf("%d %d",&n,&k);
for(i=1;i<=n;++i)
{
scanf("%d %d",&a[i],&b[i]);
p[i]=number(a[i]-b[i],a[i]+b[i],i);
}
sort(p+1,p+n+1,cmp);
for(i=1;i<=n;++i)
sum[i]=sum[i-1]+p[i].y;
f[0][1001][0]=1;
for(i=1;i<=n;++i)
{
if(!first[p[i].x+51])
first[p[i].x+51]=i;
last[p[i].x+51]=i;
}
for(i=1;i<=101;++i)
{
for(j=0;j<=2003;++j)
for(l=0;l<=k;++l)
{
if(!f[i-1][j][l])continue;
update(f[i][j][l],f[i-1][j][l],come[i][j][l],0);
if(!last[i])continue;
for(o=1;o+l<=k && o<=last[i]-first[i]+1;++o)
{
int& np=f[i][j+o*(i-51)][o+l];
update(np,f[i-1][j][l]+sum[first[i]+o-1]-sum[first[i]-1],
come[i][j+o*(i-51)][o+l],o);
}
}
}
int ans1=1000000,ans2=0;
for(i=0;i<=2003;++i)
if(f[101][i][k])
{
if(abs(i-1001)<abs(ans1) || ( abs(i-1001)==abs(ans1) && f[101][i][k]>ans2) )
{
ans1=i-1001;
ans2=f[101][i][k];
}
}
--ans2;
printf("%d %d\n",(ans1+ans2)/2,(ans2-ans1)/2);
int nk=k,nd=ans1;
for(i=101;i>=1;--i)
{
for(o=1;o<=come[i][nd+1001][nk];++o)
ansq[++ansq[0]]=p[o+first[i]-1].num;
--o;
nd-=(i-51)*o;
nk-=o;
}
sort(ansq+1,ansq+ansq[0]+1);
for(i=1;i<=ansq[0];++i)
printf("%d ",ansq[i]);
printf("\n");
return 0;
}



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

历史上的今天

评论

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

页脚

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