HDOJ 1081 To The Max

题目地址:

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

汗,这题求最长子序列我居然忘了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LS(int *line)     // 正确
{
	int i;
	int temp = line[0], sum = line[0];
	for(i = 1; i<nNum; ++i)
	{
		if(temp > 0)
			temp += line[i];
		else
			temp = line[i];
		if(temp > sum)
			sum = temp;
	}
	return sum;
}

我居然记成了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int LS(int *line)   // 错误!
{
	int i;
	int temp = line[0], sum = line[0];
	for(i = 1; i<nNum; ++i)
	{
		if(sum > 0)
			temp += line[i];
		else
			temp = line[i];
		if(temp > sum)
			sum = temp;
	}
	return sum;
}

上面这个错误的随便给组数据就行了,如:
1 -2 3
按错误的是输出2~~~
结果一直WA。
而之前做过2题居然都忘了~~~~
HDOJ 1003 Max Sum
HDOJ 1231 最大连续子序列
大家可以一起做了。
代码:

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
54
 // Author: Tanky Woo
// HDOJ 1081
// Accepted 1081 15MS 224K 891B C++ Tanky Woo 
#include <iostream>
using namespace std;
 
int aMatrix[103][103];
int aLine[103];
#define INF -100000
int nNum;
 
int LS(int *line);
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &nNum) != EOF)
    {
        memset(aMatrix, 0, sizeof(aMatrix));
        int maxSum = INF;
        for(int i=0; i<nNum; ++i)
            for(int j=0; j<nNum; ++j)
                scanf("%d", &aMatrix[i][j]);
        for(int i=0; i<nNum; ++i)
        {
            memset(aLine, 0, sizeof(aLine));
            for(int j=i; j<nNum; ++j)
            {
                for(int k=0; k<nNum; ++k)
                    aLine[k] += aMatrix[j][k];
                int sum = LS(aLine);
                if(sum > maxSum)
                    maxSum = sum;
            }
        }
        printf("%d\n", maxSum);
    }
    return 0;
}
 
int LS(int *line)
{
    int i;
    int temp = line[0], sum = line[0];
    for(i = 1; i<nNum; ++i)
    {
        if(temp > 0)
            temp += line[i];
        else
            temp = line[i];
        if(temp > sum)
            sum = temp;
    }
    return sum;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注