做网站的说3年3年包括什么,保险销售的建设网站策划书,贵州省建设厅二建报名网站,公司接软件开发平台今天想到了昨天看到一道acm题目#xff0c;难度入门级别。“谁看的最多”#xff0c;题目大概是这样的#xff1a;一队列的人3 2 1 6 4 5#xff0c;数值的大小表示该人的高度。每个人只能看到前面比他高的人#xff0c;如1可以看见2、3。但是#xff0c;如果有人B比他高…今天想到了昨天看到一道acm题目难度入门级别。“谁看的最多”题目大概是这样的一队列的人3 2 1 6 4 5数值的大小表示该人的高度。每个人只能看到前面比他高的人如1可以看见2、3。但是如果有人B比他高那么他就不能看到这那个B之前比B低的人了。如5因为6比他高他只能看到6但看不到6之前的人如果之前有7、8之类比6高的5也可以看到。而4比5低也看不到。 题目想了个大概就没有想了又是卡在里动态规划的状态里。F(i)表示第i个人看到的人数。如果他前一个人比i低则i看到的最多只有一个了就是i-1。如果他比前一个高则看到的就是前i-1个人第一个比他高的人看的人数加一。如果可以快速找前面i-1的第一个比i高就可以利用动态规划的方法了。通过一个数组记录i前面的第一个比i高的位置这样就可以快速找出。 状态转移方程F(i)若i比i-1高为F(j)1j为前面的第一比i高的否则为1i0。i0看到就为0个 挫挫代码 1 int func10(int a[], int n)2 {3 int i,j;4 int maxsee;5 int *see,*tall;6 7 if (n0)8 {9 return -1;
10 }
11 see (int*)malloc(n*sizeof(int));
12 tall (int*)malloc(n*sizeof(int));
13
14 maxsee see[0] 0;
15 tall[0] -1; //之前未有比其高的
16
17 for (i1; in; i)
18 {
19 if (a[i] a[i-1])
20 {
21 for (jtall[i-1]; j0; )
22 {
23 if (a[i]a[j])
24 {
25 break;
26 }
27 jtall[j];
28 }
29 if (j-1)
30 {
31 see[i] 0;
32 tall[i] -1;
33 }
34 else
35 {
36 see[i] see[j] 1;
37 tall[i] j;
38 }
39 }
40 else //a[i]a[i-1]
41 {
42 see[i] see[i-1]1;
43 tall[i] i-1;
44 }
45
46 maxsee maxseesee[i] ? see[i] : maxsee;
47 }
48
49 free(see);
50 free(tall);
51
52 return maxsee;
53
54 } 又一题。 复习还是不给力。。。继续。。 毕。 修订2013-4-18 在不断的被虐之后发现其是这个算法的题目是ACM中一个犀利的数据结构单调栈的应用(参考博客中的另一篇文章单调栈柱形统计图中最大面积POJ 2559) 其实此问题的解决就是单调栈的思想通过记录的一些信息模拟单调栈。其算法复杂度和单调栈是一致的。转载于:https://www.cnblogs.com/legendmaner/archive/2013/03/22/2975843.html
