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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1786][Ahoi2008]Pair 配对  

2015-01-13 16:54:59|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1786: [Ahoi2008]Pair 配对

安徽的题都是神题啊QAQ
搞了快一下午总算搞出来了……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E4+10;
const int M = 100+10;
int n,m,all[M],cot[M],data[N],oldans;
int sum[2][M],f[N][M],fn;
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//printf("%f\n",(sizeof(f))/1024.0/1024);
int i,j;
n = scan();m = scan();
for(i=1;i<=n;i++){
data[i] = scan();
if(data[i]>0){
for(j=m;j>data[i];j--)
oldans += all[j];
all[data[i]]++;
}
}
//printf("%d\n",oldans);
for(i=1;i<=n;i++)
if(data[i]<0){
fn++;
for(j=1;j<=m;j++)sum[1][j] = sum[1][j-1] + (all[j] - cot[j]);
for(j=m;j;j--){
f[fn][j] = f[fn-1][j] + sum[0][j+1] + sum[1][j-1];
sum[0][j] = sum[0][j+1] + cot[j];
}
for(j=2;j<=m;j++)f[fn][j] = min(f[fn][j],f[fn][j-1]);
}else cot[data[i]]++;
//for(i=1;i<=m;i++)if(f[fn][i] < ans)ans = f[fn][i];
printf("%d\n",f[fn][m]+oldans);
return 0;
}

题解:
DP
开脑洞猜一下,感觉-1的部分可能满足单调之类。
写个暴力跑一下发现所有-1是单调不减的,这样就知道前面的决策不会影响后面的
然后证明可以从网上随便搜一下……比如这里 (我太弱没看懂
先预处理出所有固定位置的逆序对数,记为oldans
f[i][j]表示第i个-1填j的最小代价
f[i][j] = min{f[i-1][1~j]} + (和前面构成的逆序对) + (和后面构成的逆序对)
  评论这张
 
阅读(145)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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