1831: [AHOI2008]逆序对

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 341  Solved: 226
[Submit][Status]

Description

小可可和小卡卡想到Y岛上旅游,但是他们不知道Y岛有多远。好在,他们找到一本古老的书,上面是这样说的: 下面是N个正整数,每个都在1~K之间。如果有两个数A和B,A在B左边且A大于B,我们就称这两个数为一个“逆序对”。你数一数下面的数字里有多少个逆序对,你就知道Y岛离这里的距离是多少千米了。 比如说,4 2 1 3 3里面包含了5个逆序对:(4, 2), (4, 1), (4, 3), (4, 3), (2, 1)。 可惜的是,由于年代久远,这些数字里有一部分已经模糊不清了,为了方便记录,小可可用“-1”表示它们。比如说,4 2 -1 -1 3 可能原来是4 2 1 3 3,也可能是4 2 4 4 3,也可能是别的样子。 小可可希望知道,根据他们看清楚的这部分数字,能不能推断出这些数字里最少能有多少个逆序对。

Input

第一行两个正整数N和K。第二行N个整数,每个都是-1或是一个在1~K之间的数。

Output

一个正整数,即这些数字里最少的逆序对个数。

Sample Input

5 4
4 2 -1 -1 3

Sample Output

4

HINT

4 2 4 4 3中有4个逆序对。当然,也存在其它方案得到4个逆序对。

数据范围:
100%的数据中,N<=10000,K<=100。
60%的数据中,N<=100。
40%的数据中,-1出现不超过两次。

Source

Day1

题外话:

刚开始看错题了,看成100%数据-1不超过2个,于是想这不是sb暴力吗?于是就开始敲代码,敲完之后就悲剧了。。。

结果发现不会做。。。

一看题解忽然明白了,我靠怎么还有这样一个性质,那就是 DP了。。。自己想的时候没想到DP QAQ。。。

题解:考虑一般情况 -1有很多,爆搜就不行了,那么应该如何下手呢?

联想学过的知识,大概只有DP可以用了

但怎么DP呢?

这些填的数应该有什么性质---一列数能有什么性质?大概就是递增递减吧。。。

(吐槽:这思路也太牵强了吧。。。回答:。。。。。。)

下面我们考虑两个空 a,b ,分别填上了x,y (假设只有两个空,并且x>y)

如果我们交换 x 和 y 那么会有这样几条性质:

1.[1,a-1],[b+1,n]中的数与x,y构成的逆序对没有发生改变

2.[a+1,b-1]中 >max(x,y)的数与x,y构成的逆序对没有发生改变

3.[a+1,b-1]中 < min(x,y)的数与x,y构成的逆序对没有发生改变

4.[a+1,b-1]中处于区间(x,y)的数不再与x,y构成逆序对

5.x,y不再构成逆序对

也就是说我们交换x,y得到的答案一定会减小!

稍微推广一下就是 这些填的数单调递增,但不一定是严格的

考虑实现

for i=1 to n do

for j=1 to k do

for p=1 to j do

f[i,j]=min(f[i,j],f[i-1,p]+cost(i,j))

NO NO NO

既然考虑到cost(i,j)是固定的,我们只需要求f[i-1,1],f[i-1,2]......f[i-1,j]的最小值即可

前缀最小值优化!类似于前缀和。。。

这样状态数一共有O(N*K)个,每个状态的转移的复杂度为O(1)

代码:

 var f,g,big,sma:array[..,..] of longint;
ans,i,j,n,tot,k:longint;
a,b:array[..] of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procedure init;
begin
readln(n,k);tot:=;
for i:= to n do
begin
read(a[i]);
if a[i]=- then begin inc(tot);b[tot]:=i;end;
end;
end;
procedure main;
begin
fillchar(big,sizeof(big),);
for i:= to n do
for j:= to k do big[i,j]:=big[i-,j]+ord(a[i]>j);
fillchar(sma,sizeof(sma),);
for i:=n downto do
for j:= to k do sma[i,j]:=sma[i+,j]+ord((a[i]<j) and (a[i]<>-));
fillchar(f,sizeof(f),);
for i:= to tot do
begin
f[i,]:=f[i-,]+big[b[i],]+sma[b[i],];
g[i,]:=f[i,];
for j:= to k do
begin
f[i,j]:=g[i-,j]+big[b[i],j]+sma[b[i],j];
g[i,j]:=min(g[i,j-],f[i,j]);
end;
end;
ans:=maxlongint;
for i:= to k do ans:=min(ans,f[tot,i]);
for i:= to n do inc(ans,big[i,a[i]]);
writeln(ans);
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
init;
main;
close(input);close(output);
end.

最新文章

  1. ((uchar*)(Img1-&gt;imageData + Img1-&gt;widthStep*pt.y))[pt.x] 的 具体含义
  2. 学习PYTHON之路, DAY 3 - PYTHON 基础 3 (函数)
  3. 拦截JQuery的ajax
  4. php开发环境搭建——laravel框架,apache服务器,git版本控制
  5. JS中 obj.style.left 与 obj.offsetLeft 的区别
  6. java JVM垃圾回收机制
  7. SpringMVC从一个controller跳转到另一个controller
  8. String的compareTo()方法返回值
  9. LevelDB系列之SSTable(Sorted Strings Table)文件
  10. 15_采用Pull解析器解析和生成XML内容
  11. Educational Codeforces Round 14 D. Swaps in Permutation (并查集orDFS)
  12. keystone无法查看catalog并且用户无法申请令牌的解决方案
  13. ASP.NET中登录时记住用户名和密码(附源码下载)--ASP.NET
  14. LVS+keepalived快速搭建测试环境
  15. Java多线程-线程的同步与锁【转】
  16. 用户注册之后,通过网易邮箱服务器(smtp.163.com)发送电子邮箱到注册者邮箱的的确认通知短信.(可根据需求自行调整)
  17. java发送短信验证码
  18. 全局css控制&lt;td&gt;标签属性
  19. tomcat发请求,查看各个环节的耗时时间
  20. BZOJ 3745

热门文章

  1. PHPSession-完全PHP5之session篇
  2. NewtonSoft.json 序列化和反序列化实例
  3. XMPP适配IPV6 (GCDAsyncSocket适配IPV6)
  4. iOS 多张图片保存到相册问题(add multiple images to photo album)
  5. Xcode8 Could not build Objective-C module &#39;FBSDKCoreKit&#39;
  6. 使用hwclock同步RTC(硬件时钟)和OS Clock(操作系统时钟)
  7. itoa : Convert integer to string
  8. groovy --不注意的小错误(java.lang.String.positive() is applicable)
  9. html5 canvas绘制圆形印章,以及与页面交互
  10. php缓存相关