球球网

Humble Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4742 Accepted Submission(s): 1987

Problem Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … shows the first 20 humble numbers.

Write a program to find and print the nth element in this sequence

Input
The input consists of one or more test cases. Each test case consists of one integer n with 1 <= n <= 5842. Input is terminated by a value of zero (0) for n.

Output
For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.

Sample Input
1
2
3
4
11
12
13
21
22
23
100
1000
5842
0

Sample Output
The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 4th humble number is 4.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 22nd humble number is 30.
The 23rd humble number is 32.
The 100th humble number is 450.
The 1000th humble number is 385875.
The 5842nd humble number is 2000000000.

Source
University of Ulm Local Contest 1996

今天小羊给的比赛去玩的。。
结果悲剧在这个题上。。
做好了才发现这个题其实以前做过的。。
哎。。
一开始开了2000000的数组
果断怎么做还没交就挂了
后来哥哥提醒了一句
“只存有用的”
比较有道理
这样可以省很多内存

code~

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

#include<stdio.h>
int main()
{
	int a[5843]={1};
	int i2,i3,i5,i7,t,n2,n3,n5,n7,n,i;
	i2=i3=i5=i7=0;
	t=1;
	while(t<5843)
	{
		n2=a[i2]*2;	
		n3=a[i3]*3;
		n5=a[i5]*5;
		n7=a[i7]*7;
		if(n2<n3)
			n=n2;
		else
			n=n3;
		if(n>n5)
			n=n5;
		if(n>n7)
			n=n7;
		a[t++]=n;
		if(n==n2) i2++;
		if(n==n3) i3++;
		if(n==n5) i5++;
		if(n==n7) i7++;	
	}
	while(scanf("%d",&n),n)
	{
		printf("The %d",n);
		if(n%100==11||n%10==1)
			printf("st");
		else if(n%10==2)
			printf("nd");
		else
			printf("th");
		printf(" humble number is %d.\n",a[n-1]);
	}
	return 0;
}

快变百度球了。。
伸手就被拍扁去百度谷歌了。。
发现我还是太搓了。
(1<<31)-1才是int上限
也就是0×7fffffff
一开始忘记-1了
还有要记住加括号 <<优先级太低了

发现要246题才可以刷进400+名
当然不是水的。。要做有意义的题
把lcy课件的dp1搞定了 历时太久了也。
于是加油继续做。几何还是dp2呢？。。

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

Worm
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1174 Accepted Submission(s): 756

Problem Description
自从见识了平安夜苹果的涨价后，Lele就在他家门口水平种了一排苹果树，共有N棵。

突然Lele发现在左起第P棵树上(从1开始计数)有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，Lele在苹果树旁观察了很久。虽然没有看到蝴蝶，但Lele发现了一个规律：每过1分钟，毛毛虫会随机从一棵树爬到相邻的一棵树上。

比如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫可能会在第1棵树上或者第3棵树上。如果刚开始时毛毛虫在第1棵树上，过1分钟以后，毛毛虫一定会在第2棵树上。

现在告诉你苹果树的数目N，以及毛毛刚开始所在的位置P，请问，在M分钟后，毛毛虫到达第T棵树，一共有多少种行走方案数。

Input
本题目包含多组测试，请处理到文件结束(EOF)。
每组测试占一行，包括四个正整数N,P,M,T(含义见题目描述，0

Output
对于每组数据，在一行里输出一共的方案数。
题目数据保证答案小于10^9

Sample Input
3 2 4 2
3 2 3 2

Sample Output
4
0
Hint
第一组测试中有以下四种走法：
2->1->2->1->2
2->1->2->3->2
2->3->2->1->2
2->3->2->3->2

Author
Linle

思路：
中文题 dp
题意自己看得懂就不说了
转化方程 dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
故意开大了一位 并赋值为0 就不用顾虑边界问题了

code~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<stdio.h>
int a[120][120];
int main()
{
	int N,P,M,T,i,j;
	while(scanf("%d%d%d%d",&N,&P,&M,&T)==4)
	{
		for(i=0;i<=M;i++)
			for(j=0;j<=N+1;j++)
				a[i][j]=0;
		a[0][P]=1;
		for(i=1;i<=M;i++)
			for(j=1;j<=N;j++)
				a[i][j]=a[i-1][j-1]+a[i-1][j+1];
 
		printf("%d\n",a[M][T]);
	}
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1069
Monkey and Banana
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1859 Accepted Submission(s): 960

Problem Description
A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.

The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.

They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked.

Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.

Input
The input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.

Output
For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format “Case case: maximum height = height”.

Sample Input
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

Sample Output
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

Source
University of Ulm Local Contest 1996

思路：
大意就是猴子搬箱子 拿好多箱子叠罗汉。
看高度最高有多少。
但是叠罗汉要有条件的。
下面一个箱子的长和宽必须严格大于上一个。
所以 根据这个条件，虽然每个箱子可以有无数个，
但是长宽高相同的箱子只要一个就好了
因为多了也不是严格大于，而是等于了
但每个箱子可以放多个角度
可以有3种不同的高
于是每个箱子可以构造出3个不同的箱子
所以箱子无数个还是有用的
由n个箱子变成n*3个
这n*3个箱子先排序 然后用类似lis的思路dp
哎。。有一点想不明白。为什么总是要排序呢
只知道不排序是不对的 想起来就奇怪 然后样例也只能过两个
于是还是排序了 然后1Y

给code~

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
55
56
57
58

#include<cstdio>
#include<algorithm>
using namespace std;
#define swap(a,b) {a^=b;b^=a;a^=b;}
struct node
{
	int x,y,z;
}f[100];
bool cmp(node a,node b)
{
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}
int main()
{
	int dp[100],n,t,i,j,a,b,c,max,flag=0;
	while(scanf("%d",&n),n)
	{
		t=0;
		for(i=0;i<n;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(a>b) swap(a,b);
			if(a>c) swap(a,c);
			if(b>c) swap(b,c);
			f[t].x=a;
			f[t].y=b;
			f[t].z=c;
			t++;
			f[t].x=a;
			f[t].y=c;
			f[t].z=b;
			t++;
			f[t].x=b;
			f[t].y=c;
			f[t].z=a;
			t++;
		}
		sort(f,f+t,cmp);
		dp[0]=f[0].z;
		for(i=1;i<t;i++)
		{
			dp[i]=0;
			for(j=0;j<i;j++)
				if(f[j].x<f[i].x&&f[j].y<f[i].y)
					if(dp[j]>dp[i])
						dp[i]=dp[j];
			dp[i]+=f[i].z;
		}
		max=0;
		for(i=0;i<t;i++)
			if(dp[i]>max)
				max=dp[i];
		printf("Case %d: maximum height = %d\n",++flag,max);
	}
	return 0;
}

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

产生冠军
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2285 Accepted Submission(s): 1138
Problem Description
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

Input
输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output
对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output
Yes
No

Author
qianneng

Source
迎接新学期——超级Easy版热身赛

Recommend
lcy

思路：
就是找一次都没输过的
如果有而且是一个人 就Yes
否则No
还是很不服气。。
为什么输一次就不能当冠军了
为什么没有翻身的机会。
不过没找到反例
目前先认为这样好了。。
路过神人谁来指点我下吧

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

#include<iostream>
#include<string>
using namespace std;
int num;
string c[1005];
int p[1005];
int find(string s)
{
	int i;
	for(i=0;i<num;i++)
		if(c[i]==s)
		{
			return i;
		}
	c[num]=s;
	num++;
	return num-1;
}
int main()
{
	string a,b;
	int i,t,ti,n,flag;
 
	while(scanf("%d",&n)!=EOF,n)
	{
		num=0;
		for(i=0;i<n;i++)
			p[i]=0;
		for(i=0;i<n;i++)
		{
			cin>>a>>b;
			t=find(a);
			t=find(b);
			p[t]=1;
		}
		t=0;
		for(i=0;i<num;i++)
		{
			if(p[i]==0)
				t++;
		}
		if(t==1)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}

1
2
3
4
5
6
7
8

memset(Isp,true,sizeof(Isp));
pn=0;
for(i=2;i<=maxn;++i)
{
	if(Isp[i])p[pn++]=i;
	for(j=i*i;j<=maxn;j+=i)
		Isp[j]=false;
}

一开始觉得奇怪的是 为什么j要从i*i开始
至少也要i*1 i*2的递加啊
原来是这样子的
因为j=i*i如果变成i*k 而k 那么一定在前面的k*k中被筛选掉了
于是可以放心的用啦

p.s
1.高斯猜测，n以内的素数个数大约与n/ln(n)相当，或者说，当n很大时，两者数量级相同。这就是著名的素数定理。　　
2.十七世纪费马猜测，2的2^n次方+1，n=0，1，2…时是素数，这样的数叫费马素数，可惜当n=5时，2^32+1就
不是素数，至今也没有找到第六个费马素数。
3.18世纪发现的最大素数是2^31-1，19世纪发现的最大素数是2^127-1，20世纪末人类已知的最大素数是2^859433-1，用十进制表示，这是一个258715位的数字。
4.孪生素数猜想：差为2的素数有无穷多对。目前知道的最大的孪生素数是1159142985×2^2304－1和1159142985×2^2304＋1。
5. 歌德巴赫猜想：大于2的所有偶数均是两个素数的和，大于5的所有奇数均是三个素数之和。其中第二个猜想是第一个的自然推论，因此歌德巴赫猜想又被称为1+ 1问题。我国数学家陈景润证明了1+2，即所有大于2的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。

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

FatMouse’s Speed
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2626 Accepted Submission(s): 1099
Special Judge
Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed.

Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],…, m[n] then it must be the case that

W[m[1]] < W[m[2]] < ... < W[m[n]]
and
S[m[1]] > S[m[2]] > … > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.

Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Sample Output
4
4
5
9
7

Source
Zhejiang University Training Contest 2001

首先建立结构体。每个老鼠：重量，速度，编号。
然后排序 ：重量递增 速度递减
之后lis 同时要注意保存路径 即from
便于等下输出

以下是code

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
55
56
57
58
59
60
61

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int w,s,no;
}a[1005];
bool cmp(node a,node b)
{
	if(a.w==b.w)
		return a.s>b.s;
	return a.w<b.w;
}
int main()
{
	int i=0,j,n,max,t;
	int dp[1005],from[1005];
	while(scanf("%d%d",&a[i].w,&a[i].s)!=EOF)
	{
		a[i].no=i+1;
		i++;
	}
	n=i;
	sort(a,a+n,cmp);
	dp[0]=1;
	for(i=1;i<n;i++)
	{
		dp[i]=1;
		for(j=0;j<i;j++)
		{
			if(a[j].w<a[i].w&&a[j].s>a[i].s)
				if(dp[j]+1>=dp[i])
				{
					dp[i]=dp[j]+1;
					from[i]=j;
				}
		}
	}
	max=0;
	j=-1;
	for(i=0;i<n;i++)
	{
		if(max<dp[i])
		{
			max=dp[i];
			j=i;
		}
	}
	t=j;
	j=1;
	printf("%d\n",max);
	for(i=0;i<max;i++)
	{
		dp[max-j]=t;
		j++;
		t=from[t];
	}
	for(i=0;i<max;i++)
		printf("%d\n",a[dp[i]].no);
	return 0;
}

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

最少拦截系统
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3878 Accepted Submission(s): 1382

Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input
8 389 207 155 300 299 170 158 65

Sample Output
2

Source
浙江工业大学第四届大学生程序设计竞赛

思路：
挂了好久的题 终于A掉了。用了两种方法诶。。
终于A掉了 好开心。
本题直接用lis做就好了
一开始不理解 哥哥给了我如下结论：
“最少非递增序列覆盖数等于 最长递增子序列长度”
然后直接lis做的
后来发现确实结论成立的
我们要求需要多少套设备 其实也就是求上升序列的长度。
因为如果后面来的导弹高度比前面的低 那么可以借助该套设备来挡导弹
如果高于前面的高度 则必须另外购置一套设备
设备数+1。也就是长度+1。

或者换种说法。只要导弹高度低的，就可以用前面已有设备来挡。
那么就可以无视掉了。。于是剩下的就都是上升序列了。
于是我们直接求lis长度即可。

下面给代码
第一个是lis做的
第二个是按题意来模拟的

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

#include<stdio.h>
int main()
{
	int n,i,j,max,a[1100],dp[1100];
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		dp[0]=1;
		max=0;
		for(i=1;i<n;i++)
		{
			dp[i]=1;
			for(j=0;j<i;j++)
			{
				if(a[j]<a[i])
					if(dp[j]+1>dp[i])
					{
						dp[i]=dp[j]+1;
						if(max<dp[i])
							max=dp[i];
					}
			}
		}
		printf("%d\n",max);
	}
	return 0;
}

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

#include<stdio.h>
int main()
{
	int n,i,j,count,mm,a[1100];
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		i=0;count=0;
		while(i<n)
		{
			mm=35000;
			count++;
			for(j=0;j<n;j++)
			{
 
				if(a[j]!=-1&&a[j]<mm)
				{
					mm=a[j];
					a[j]=-1;
					i++;
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

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

免费馅饼
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7003 Accepted Submission(s): 2254

Problem Description
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）

Input
输入数据有多组。每组数据的第一行为以正整数n(0

Output
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。

Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0

Sample Output
4

Author
lwg

code~

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

#include<stdio.h>
int f[100005][11];
int fab(int a)
{
	if(a<0) a=-a;
	return a;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int m,x,T,mmax,i,j,mm;
	while(scanf("%d",&m)!=EOF,m)
	{
		for(i=0;i<100005;i++)
			for(j=0;j<11;j++)
				f[i][j]=0;
		mmax=0;
		while(m--)
		{
			scanf("%d%d",&x,&T);
			f[T][x]++;
			if(T>mmax) mmax=T;
		}
		mm=-1;
		for(i=1;i<=mmax;i++)
		{
			for(j=0;j<11;j++)
			{
				if(fab(j-5)<=i)/*为了保证是从0秒5处开始的。
				1秒时可以在456，2秒可以在34567。于是规律是fab(j-5)<=i */
				{
					if(j==0)
						f[i][j]=f[i][j]+max(f[i-1][j],f[i-1][j+1]);
					else if(j==10)
						f[i][j]=f[i][j]+max(f[i-1][j],f[i-1][j-1]);
					else
						f[i][j]=f[i][j]+max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1]);
					if(mm<f[i][j]) mm=f[i][j];
				}
 
			}
		}
		printf("%d\n",mm);
	}
}

从mmax秒到0秒 逆向写也可以过。而且好像更方便些呢。
因为规定是从0秒5处开始的。于是最后只要输出f[0][5]即可。
代码前面加上一行

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

#include<stdio.h>
int f[100005][11];
int fab(int a)
{
	if(a<0) a=-a;
	return a;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int m,x,T,mmax,i,j,mm;
	while(scanf("%d",&m)!=EOF,m)
	{
		for(i=0;i<100005;i++)
			for(j=0;j<11;j++)
				f[i][j]=0;
		mmax=0;
		while(m--)
		{
			scanf("%d%d",&x,&T);
			f[T][x]++;
			if(T>mmax) mmax=T;
		}
		mm=-1;
		for(i=mmax;i>0;i--)
		{
			for(j=0;j<11;j++)
			{
				if(j==0)
					f[i-1][j]=f[i-1][j]+max(f[i][j],f[i][j+1]);
				else if(j==10)
					f[i-1][j]=f[i-1][j]+max(f[i][j],f[i][j-1]);
				else
					f[i-1][j]=f[i-1][j]+max(max(f[i][j],f[i][j-1]),f[i][j+1]);
			}
		}
		printf("%d\n",f[0][5]);
	}
}

Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 41848 Accepted Submission(s): 9136

Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1:
14 1 4

Case 2:
7 1 6

Author
Ignatius.L

思路：
s在这里表示到包含第i位的最大的和
第一 要包含i
第二 要是最大。。
因此 每经过一个数 必须考虑它对后面的影响
如果当前这个s小于0了
那么对后面的数会变差
因此就要把s变为0
反之 按照我们的定义 肯定可以取得最好的结果
每次用新的s去更新那个max
最后的那个max就是最优值嘛
对于一个i ， 我们知道了包含它的最优值s
那么也要知道这个s的起点
按照我们刚才所说的
既然s小于0了
那么现在的这个i就不能对后面的数产生影响了
也就是后面数的s的起点肯定不是i额
所以就将k变成了i+1

code~

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

#include<stdio.h>
int main()
{
	int max,n,m,i,t,s,start,end,j,k;
	while(scanf("%d",&n)!=-1)     
	{
		for(j=1;j<=n;j++)
		{
			s=0;max=-9999;
			scanf("%d",&m);
			for(k=i=1;i<=m;i++) 
			{
				scanf("%d",&t);
				s+=t;
				if(s>max)
				{
					max=s;
					start=k;
					end=i;
				}
				if(s<0)
				{
					k=i+1;
					s=0;
				}
			}
			printf("Case %d:\n%d %d %d\n",j,max,start,end);
			if(n-j)
				printf("\n");  
		}
	} 
	return 0;  
}