hdu-4561 连续最大积( 水题)

http://acm.hdu.edu.cn/showproblem.php?pid=4561

求连续最大积。

他妈的狗逼思路到底咋说。。。。。

思路是 %&*（）*（&……））*）*&）……%……%**（*（）（）——+（**（……&*……%&*……Y%^&%%^*&&（&*（&*（*&（）*&（**……&%……&

%&……%&……&（&……* （））&（**&……%*&&*（（——+——）&（**……&%……&……*&%￥S%^&$**&%%&^A *&^&***(^U(*)()^(*&^&*(()&^**&*$%YT^&^%&^^&%%^%&%^&%&^

%&^&(^&&(*&_)(&^*^U&*&OP)_(+_{()*&*&%^&%$&^$^%$#%^&*^&)(**)_(_+................................................

懂了吧。。。。。

我来翻译；

其实思路就是找断点，断点就是0，也就是以0为分界，将所给的数字串分成k段比如2220-2-2-22022；

就可以分成222 -2-2-22 22三段，因为如果选入0的话乘积肯定是0，题目说积小于等于0的结果都为0，所以以0分界。

那么就是计算每段的2的个数，和-2的个数，如果段内的-2个数是偶数个，那么这段的长度直接和maxx比较，更新maxx,

如果是奇数个，假设n个的话从段的左边循环到有边直到遇到第n个-2跳出，那么前面不就是偶数个-2了么。

那么再从右端循环到左端，直到遇到第n个-2跳出，比较两次的大小，大的就是本段连续最大积。

因为要连续而且又只多一个-2，所以说最大要么左连续，要么右连续。

最后maxx就是最大的了；

 1 #include<stdio.h>

 2 #include<iostream>

 3 #include<stdlib.h>

 4 #include<string.h>

 5 #include<math.h>

 6 typedef struct pp

 7 {

 8     int x;

 9     int y;

10     int x1;

11     int y1;

12 } ss;

13 using namespace std;

14 int main(void)

15 {

16     int a[10005];

17     ss cou[10005];

18     int n,i,j,k,p,q;

19     scanf("%d",&n);

20     for(i=1; i<=n; i++)

21     {

22         scanf("%d",&k);

23         for(j=0; j<k; j++)

24         {

25             scanf("%d",&a[j]);

26             cou[j].x=0;

27             cou[j].y=0;

28             cou[j].x1=0;

29             cou[j].y1=0;

30         }

31         if(a[0]>0)

32         {

33             cou[0].x++;

34         }

35         else if(a[0]<0)

36         {

37             cou[0].y++;

38         }

39         int maxx=0;

40         for(j=1; j<k; j++)//从断点到到本个点有多2 -2(从左循环)

41         {

42             if(a[j]>0)

43             {

44                 cou[j].x=cou[j-1].x+1;

45                 cou[j].y=cou[j-1].y;

46             }

47             else if(a[j]<0)

48             {

49                 cou[j].y=cou[j-1].y+1;

50                 cou[j].x=cou[j-1].x;

51             }

52

53         }

54         if(a[k-1]>0)

55         {

56             cou[k-1].x1++;

57         }

58         else if(a[k-1]<0)

59         {

60             cou[k-1].y1++;

61         }

62         for(j=k-2; j>=0; j--)//从断点到到本个点有多2 -2(从右循环)

63         {

64             if(a[j]>0)

65             {

66                 cou[j].x1=cou[j+1].x1+1;

67                 cou[j].y1=cou[j+1].y1;

68             }

69             else if(a[j]<0)

70             {

71                 cou[j].y1=cou[j+1].y1+1;

72                 cou[j].x1=cou[j+1].x1;

73             }

74

75         }

76         for(j=0; j<k; j++)

77         {

78             if(cou[j].y%2==0)

79             {

80                 if(maxx<cou[j].x+cou[j].y)

81                 {

82                     maxx=cou[j].x+cou[j].y;

83                 }

84             }

85             if(cou[j].y1%2==0)

86             {

87                 if(maxx<cou[j].x1+cou[j].y1)

88                 {

89                     maxx=cou[j].x1+cou[j].y1;

90                 }

91             }

92         }

93         printf("Case #%d: %d\n",i,maxx);

94     }

95     return 0;

96 }

巴特西

hdu-4561 连续最大积( 水题)

最新文章

热门文章