http://acm.nyist.net/JudgeOnline/problem.php?pid=236
这道题,华丽丽的坑了我六个小时的时间。
参考了一下其他的blog,发现原来用的diworth定理。
先将一边排好序,然后,对另一个参数构成的序列,求最长单调递减子序列即可以。
一开始我用的dp双重循环,虽然感觉时间有点危险,但是图省事,提交上去。瞬间tle了。只好改写为栈优化的最长单调递减子序列。
首先卡壳在了二分查找哪里,看到一篇文章说90%的人都写不对二分查找,然后写啊写啊,一直提交一直错,以为自己的二分查找写错了。
但是我改啊改啊,怎么就是找不到错,感觉不对劲然后找了另外一道题,http://acm.nyist.net/JudgeOnline/problem.php?pid=17,试了一下,发现自己的二分查找没有写错,那么应该是我的逻辑有错误了,发现自己对diworth定理理解的不是很深刻,然后回头想了一下,也没发现问题,然后又找了道题一导弹防御的问题一试果然有问题。然后开始琢磨怎么回事,最后突然想是不是栈优化的地方出了问题,发现果然是哪里出现了问题。最后总结了一下栈应该怎么用。
1 2
| 如果是严格单调下降的子序列。在栈中应该替换最先小于等于此值的位置的值。而如果求的不是严格单调下降的子序列。在栈中应该替换最先小于此值的位置的值。 反之,求上升的子序列时也是这样。也是可以这样理解,严格的升序或降序则不能有重复的值在栈中,不严格的升序或降序则可以有重复的值。
|
修改完栈的错误后,直接把导弹防御的问题给AC了,但是这道题还是有错误,这时候我的个心真是哇凉哇凉的了,然后看讨论区吧,突然发现一句话,说此题要好好看题,瞬间我想是不是我没理解好题意,或者是有哪里漏想了,发现有一句话有意思了,是每一个参数都要小于等于另外一个参数,然后我想是不是少考虑了,有一个参数相等的情况。因为相等的情况下,这时这些木棍只需要一个时间就可以了,发现cmp哪里果然有问题。改完后,瞬间过了。哈哈。。
总之很开心啊,哈哈,明天考电磁场了,今天真给鼓劲啊,哈哈。。。
cmp原先是: 1 2 3 4 5
| int cmp(M a,M b) { return a.weight<b.weight; }
|
AC代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; typedef struct{ int weight; int len; }M; int q(int *num,int B,int E,int elem) { if(B>=E) return E; int mid = (B+E)/2; if(num[mid]>elem) return q(num,mid+1,E,elem); else return q(num,B,mid,elem); } int cmp(M a,M b) { if(a.weight==b.weight) return a.len<b.len; else return a.weight<b.weight; } int main() { int t,num[5005]; int tm,top = 0; M input[5005]; scanf("%d",&t); while(t--) { scanf("%d",&tm); for(int i = 0;i<tm;++i) scanf("%d%d",&input[i].len,&input[i].weight); sort(input,input+tm,cmp); top = 0; num[0] = input[0].len; ++top; for(int i = 1; i < tm;++i) { if(input[i].len<num[top-1]) { num[top++]=input[i].len; }else{ num[q(num,0,top-1,input[i].len)]=input[i].len; } } printf("%d\n",top); } return 0; }
|