算法分析与设计(二)

http://192.168.173.163/JudgeOnline/contest.php?cid=1251

密码:123654

算法作业2

单词排序

题目描述

小红学会了很多英文单词,妈妈为了帮小红加强记忆,拿出纸、笔,把 N 个单词写在纸上的一行里,小红看了几秒钟后,将这张纸扣在桌子上。妈妈问小红:“你能否将这 N 个单词按照字典排列的顺序,从小到大写出来?”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意:所有单词都由小写字母组成,单词两两之间用一个空格分隔。

输入

输入包含两行。

第一行仅包括一个正整数N(0<N≤26)。

第二行包含N个单词,表示妈妈写出的单词,两两之间用一个空格分隔。

单个单词长度不超过1010。

输出

输出仅有一行。针对妈妈写出的单词,按照字典排列的顺序从小到大排列成一行的结果,每个单词后带一个空格。

样例输入

1
2
4
city boy tree student

样例输出

1
boy city student tree

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<algorithm>
using namespace std;

int main(){
int n;
cin >> n;
string s[27];
for (int i = 0; i < n; i++) {
cin >> s[i];
}
sort(s, s + n);
for (int i = 0; i < n; i++) {
cout << s[i] << " ";
}
cout << endl;
}

求数组的最长递减子序列

题目描述

给定一个整数序列,输出它的最长递减(注意不是“不递增”)子序列。

输入

输入包括两行,第一行包括一个正整数N(N<=1000),表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数,整数范围区间为[-30000,30000]。

输出

输出最长递减子序列,数字之间有一个空格。

样例输入

1
2
8
9 4 3 2 5 4 3 2

样例输出

1
9 5 4 3 2

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;
int num[1005];
int dp[1005];
int pre[1005];
int main(){
int n,i,j;
while(scanf("%d",&n)!=EOF){
memset(dp,1,sizeof(dp));
memset(pre,-1,sizeof(pre));
for ( i = 0; i < n; ++i) {
scanf("%d",&num[i]);
}
for ( i = 1; i < n; ++i)
{
for ( j = 0; j < i; ++j)
{
if(num[i]<num[j]&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
pre[i]=j;
}
}
}
int maxlen=0;
for ( i = 0; i < n; ++i)
{
if (maxlen<dp[i])
{
maxlen=dp[i];
j=i;
}
}
stack<int> v;
while(j!=-1){
v.push(num[j]);
j=pre[j];
}
printf("%d", v.top());
v.pop();
while(!v.empty()){
printf(" %d", v.top());
v.pop();
}
printf("\n");

}
return 0;
}

矩形滑雪场

题目描述

zcb喜欢滑雪。他来到了一个滑雪场,这个滑雪场是一个矩形,为了简便,我们用r行c列的矩阵来表示每块地形。为了得到更快的速度,滑行的路线必须向下倾斜。 例如样例中的那个矩形,可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1,其实25-24-23…3-2-1更长,事实上这是最长的一条。

输入

第1行:两个数字r,c(1 ≤ r, c ≤ 100),表示矩阵的行列。第2..r+1行:每行c个数,表示这个矩阵。

输出

仅一行:输出1个整数,表示可以滑行的最大长度。

样例输入

1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

1
25

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
#include<bits/stdc++.h>
using namespace std;

int r, c;
int s[101][101];
int d[101][101];
int x[4] = { 1,-1,0,0 };
int y[4] = { 0,0,1,-1 };

int dfs(int a,int b) {
if (d[a][b] != -1) {
return d[a][b];
}
int ans = 0;
for (int i = 0; i < 4; i++) {
int xx = a + x[i];
int yy = b + y[i];
if (xx >= 0 && xx < r && yy >= 0 && yy < c && s[xx][yy] < s[a][b]) {
ans = max(ans, dfs(xx, yy));
}
}
//d[a][b] = ans + 1;
return d[a][b] = ans + 1;
}

int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> s[i][j];
}
}
memset(d, -1, sizeof(d));
int ans = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (d[i][j] == -1) {
ans = max(ans, dfs(i, j));
}
}
}
cout << ans << endl;
return 0;
}

Homework

题目描述

临近开学了,大家都忙着收拾行李准备返校,但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上:目前为止还未开动。

暑假作业是很多张试卷,我们这些从试卷里爬出来的人都知道,卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少,但又因为选择题题目都普遍很长。如果有 5 张试卷,其中 4 张是选择题,最后一张是填空题,很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题,虽然工作量很少,但表面上看起来也已经做了4/5的作业了。

I_Love_C决定就用这样的方法来蒙混过关,他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值(按上面的原理,选择题越多价值当然就越高咯)。

现在就请你帮他安排一下,用他仅剩的一点时间来做最有价值的作业。

输入

测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头,分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行,每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值,输入以 0 0 结束。

输出

对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位

提示:float 的精度可能不够,你应该使用 double 类型。

样例输入

1
2
3
4
5
6
4 20
4 10
5 22
10 3
1 2
0 0

样例输出

1
37.00

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
#include<bits/stdc++.h>
using namespace std;
int m, n;
struct work {
double w;
double v;
}s[21];

bool cmp(work a, work b) {
return (a.v / a.w) > (b.v / b.w);
}
int main() {
while (cin >> m >> n) {
if (m == 0 && n == 0) {
return 0;
}
double result = 0;
for (int i = 0; i < m; i++) {
cin >> s[i].w >> s[i].v;
}
sort(s, s + m, cmp);
for (int i = 0; i < m; i++) {
if (n == 0) break;
if (n >= s[i].w) {
n -= s[i].w;
result += s[i].v;
}
else {
result += (n / s[i].w) * s[i].v;
n = 0;
}
}
cout << fixed << setprecision(2) << result << endl;
}
return 0;
}

区间包含问题

题目描述

已知 n 个左闭右开区间 [a,b),对其进行 m 次询问,求区间[l,r]最多可以包含 n 个区间中的多少个区间,并且被包含的所有区间都不相交。

输入

输入包含多组测试数据,对于每组测试数据:

第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。

接下来 n 行每行包含两个整数 a ,b (0≤a<b≤10^9) 。

接下来 m 行每行包含两个整数 l ,r (0≤l<r≤10^9) 。

输出

对于每组测试数据,输出 m 行,每行包含一个整数。

数据过大请使用快速输入输出

样例输入

1
2
3
4
5
6
7
8
4 3
1 3
2 4
1 4
1 2
1 2
1 3
1 4

样例输出

1
2
3
1
1
2

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
#include<bits/stdc++.h>
using namespace std;
struct node {
int l;
int r;
};
bool cmp(node a, node b) {
return a.r < b.r;
}
int main() {
std::ios::sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
node* nnum = new node[n];
node* mnum = new node[m];
for (int i = 0; i < n; i++) {
cin >> nnum[i].l >> nnum[i].r;
}
for (int i = 0; i < m; i++) {
cin >> mnum[i].l >> mnum[i].r;
}
sort(nnum, nnum + n, cmp);
for (int i = 0; i < m; i++) {
int k = mnum[i].l;
int ans = 0;
for (int j = 0; j < n; j++) {
if (k <= nnum[j].l) {
if (mnum[i].r >= nnum[j].r) {
ans++;
k = nnum[j].r;
}
else {
break;
}
}
}
cout << ans << endl;
}
delete[] nnum;
delete[] mnum;
}
return 0;
}

最长子序列

题目描述

在一个数组中找出和最大的连续几个数。(至少包含一个数)

例如:数组A[] = [-2,1,-3,4,-1,2,1,-5,4],则连续的子序列[4,-1,2,1]有最大的和6

输入

第一行输入一个不超过1000的整数n。

第二行输入n个整数A[i]。

输出

输出一个整数,表示最大的和。

样例输入

1
2
3
1 1 -2

样例输出

1
2

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
#include <iostream>
#include<algorithm>
using namespace std;
int cmp(int a, int b) {
return b < a;
}

int a[1002] = { 0 };
int b[1002] = { 0 };

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
b[1] = a[1];
for (int i = 1; i <= n; i++) {
if (b[i - 1] > 0) { b[i] = b[i - 1] + a[i]; }
else b[i] = a[i];
}
sort(b + 1, b + n + 1, cmp);
cout << b[1] << endl;
return 0;
}

元素整除问题

题目描述

输入20个整数,输出其中能被数组中其它元素整除的那些数组元素。

输入

输入20个整数

输出

按输入顺序输出符合要求的数字,每行输出一个整数。

样例输入

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

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
4
6
8
9
10
12
14
15
16
18
20
21

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
#include<iostream>
using namespace std;

int main() {
int a[21];
int c[21] = { 0 };
for (int i = 0; i < 20; i++) {
cin >> a[i];
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
if (a[j] != 0 && a[i] % a[j] == 0 && a[i]!=a[j]) {
c[i] = 1;
break;
}
else c[i] = 0;
}
}
for (int i = 0; i < 20; i++) {
if (c[i] != 0) {
cout << a[i] << endl;
}
}
return 0;
}

渊子赛马

题目描述

赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到达齐国国都。 赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王,下到大臣,常常以赛马取乐,并以重金赌输赢。田忌多次与国王及其他大臣赌输赢,屡赌屡输。一天他赛马又输了,回家后闷闷不乐。孙膑安慰他说:“下次有机会带我到马场看看,也许我能帮你。” 孙膑仔细观察后发现,田忌的马和其他人的马相差并不远,只是策略运用不当,以致失败。 比赛前田忌按照孙膑的主意,用上等马鞍将下等马装饰起来,冒充上等马,与齐王的上等马比赛。第二场比赛,还是按照孙膑的安排,田忌用自己的上等马与国王的中等马比赛,在一片喝彩中,只见田忌的马竟然冲到齐王的马前面,赢了第二场。关键的第三场,田忌的中等马和国王的下等马比赛,田忌的马又一次冲到国王的马前面,结果二比一,田忌赢了国王。 就是这么简单,现在渊子也来赛一赛马。假设每匹马都有恒定的速度,所以速度大的马一定比速度小的马先到终点(没有意外!!)。不允许出现平局。最后谁赢的场数多于一半(不包括一半),谁就是赢家(可能没有赢家)。渊子有 N(1<=n<=1000)匹马参加比赛。对手的马的数量与渊子马的数量一样,并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果,看看渊子能否赢得比赛。

输入

输入有多组测试数据。 每组测试数据包括 3 行: 第一行输入 N。表示马的数量。 第二行有 N 个整型数字,即渊子的 N 匹马的速度。 第三行有 N 个整型数字,即对手的 N 匹马的速度。 当 N 为 0 时退出。

输出

若通过聪明的你精心安排,如果渊子能赢得比赛,那么输出YES。 否则输出NO。

样例输入

1
2
3
4
5
6
7
5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0

样例输出

1
2
YES
NO

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
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
int a[1002];
int b[1002];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
sort(a, a + n);
sort(b, b + n);
int w = 0;
for (int i = 0, j = 0; i < n; i++) {
if (a[i] > b[j]) {
w++;
j++;
}
}
if (w > n / 2) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}

最长上升子序列

题目描述

给定一个长度为n的字符串S(只包含小写字母),给出q次查询,对于每次查询x,求出以S[x](下标从0开始)为起始的最长上升子序列的长度(严格增)。

输入

第一行两个整数n,q(1<=n,q<=1e5),意义见题目描述。

第二行一个长度为n的字符串S。

第三行q个整数x(0<=x<n),表示q次查询。

输出

输出q个数(以空格分割,行末有空格),表示以S[x]为起始的最长上升子序列的长度。

样例输入

1
2
3
10 3
abbaaccbbd
2 5 8

样例输出

1
3 2 2

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
#include<bits/stdc++.h>
using namespace std;
int n, q, x;
char a[100001];
int ans[100001];
int p[27];
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = n - 1; i >= 0; i--) {
ans[i] = 1;
for (int j = a[i] - 'a' + 1; j < 26; j++)
ans[i] = max(ans[i], p[j] + 1);
p[a[i] - 'a'] = ans[i];
}
while (q--) {
cin >> x;
cout<<ans[x]<<" ";
}
return 0;
}

区间第k小

题目描述

花花上算法课又偷偷摸鱼。她今天刚学会如何求解区间第k小的数,但是感觉没什么意思。于是她将题目稍稍改动了一下:对于一个长度为n的数列a来说,一共有n*(n+1)/2个子区间,对于数列a的每一个子区间,如果这个子区间的长度小于k,我们不管它,否则把该子区间的第k小的数加入新数列b(初始为空)。花花并不关心数列b里面的元素是什么,她只想知道新数列b中第k小的元素是多少。

例如,一个长度为4的数列a={5,3,4,9},当k取3时只有三个子区间长度是>=3的:{5,3,4},{3,4,9}和{5,3,4,9}。分别提取各自的第3小的数加入b数列得到{5,9,5},其中第3小的数为9。

输入

第一行两个数n,k(1<=n, k<=1e5)意义见题目描述

第二行n个数表示数列a中的元素ai。(1<=ai<=1e9)

数据保证数列b中的元素个数不少于k个

输出

输出一个数,表示数列b中的第k小的数

样例输入

1
2
4 3
5 3 4 9

样例输出

1
9

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
#include <algorithm>
#include<iostream>
using namespace std;

int n, k;
long long a[100001];
long long b[100001];
bool check(long long x) {
int l = 0, r = -1;
int count = 0;
long long ans = 0;
while (r <n && l <n ) {
if (count < k) {
if (a[r + 1] <= x && r + 1 < n) count++;
r++;
}
else {
if (count == k) ans += (n - r);
if (ans >= k) return 1;
if (a[l] <= x) count--;
l++;
}
}
return 0;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b, b + n);
int l = 0, r = n - 1;
int mid;
int ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (check(b[mid])) {
ans = b[mid];
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}

算法实验2

最长公共子序列

题目描述

一个序列X和另一个序列Z,当Z中的所有元素都在X中存在,并且在X中的下标顺序是严格递增的,那么就把Z叫做X的子序列。
例如:Z=是序列X=的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。
现给两个序列X和Y,请问它们的最长公共子序列的长度是多少?

输入

输入包含多组测试数据。每组输入占一行,为两个字符串,由若干个空格分隔。每个字符串的长度不超过100。

输出

对于每组输入,输出两个字符串的最长公共子序列的长度。

样例输入

1
2
3
abcfbc abfcab
programming contest
abcd mnp

样例输出

1
2
3
4
2
0

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main() {
int m[103][103];
string s, t;
while (cin >> s >> t) {
memset(m, 0, sizeof(m));
int result = 0;
s = '0' + s;
t = '0' + t;
for (int i = 1; i < s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if (s[i] != t[j]) m[i][j] = max(m[i - 1][j], m[i][j - 1]);
else m[i][j] = m[i - 1][j - 1] + 1;
result = max(result, m[i][j]);
}
}
cout << result << endl;
}
return 0;
}

矩阵连乘

题目描述

给定n个矩阵{A1,A2,…,An},及m个矩阵连乘的表达式,判断每个矩阵连乘表达式是否满足矩阵乘法法则,如果满足,则计算矩阵的最小连乘次数,如果不满足输出“MengMengDa“。

输入

输入数据由多组数据组成(不超过10组样例)。每组数据格式如下:
第一行是2个整数n (1≤n≤26)和m(1≤m≤3),表示矩阵的个数。
接下来n行,每行有一个大写字母,表示矩阵的名字,后面有两个整数r和c,分别表示该矩阵的行数和列数,其中1<r, c<100。
第n+1行到第n+m行,每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。

输出

对于每个矩阵连乘表达式,如果运算不满足矩阵乘法法则的情况(即左矩阵列数与右矩阵的行数不同),则输出“MengMengDa”,否则输出最小矩阵连乘次数。

数据保证结果不超过1e9。

样例输入

1
2
3
4
5
6
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC

样例输出

1
2
7500
MengMengDa

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;

int m[102][102] = { 0 };
int p[200];

int MatrixChain(int n){
for (int i = 1; i <= n; i++)
m[i][i] = 0;
for (int r = 2; r <= n; r++){
for (int i = 1; i <= n - r + 1; i++){
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
for (int k = i + 1; k < j; k++){
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j])
m[i][j] = t;
}
}
}
return m[1][n];
}

int main(){
int n, m;
while (cin >> n >> m){
char matrix[27];
int row[27];
int col[27];
for (int i = 0; i < n; i++)
cin >> matrix[i] >> row[i] >> col[i];
char test[3][102];
for (int i = 0; i < m; i++){
cin >> test[i];
}
int key;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (test[i][0] == matrix[j]){
key = j;
break;
}
}
p[0] = row[key];
p[1] = col[key];
int len = strlen(test[i]);
int flag = 1;
for (int k = 1; k < len; k++){
for (int j = 0; j < n; j++){
if (test[i][k] == matrix[j]){
key = j;
break;
}
}
if (p[k] == row[key])
p[k + 1] = col[key];
else
{
cout << "MengMengDa" << endl;
flag = 0;
break;
}
}
if (flag == 1)
cout << MatrixChain(len) << endl;
}
}
}

01背包问题

题目描述

已知有N种物品和一个可容纳C重量的背包。每种物品i的重量为Wi,价值为Pi。那么,采用怎样的装包方法才会使装入背包物品的总价值最大。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=10),代表测试数据个数。

接下来有T组测试数据。每组测试数据第一行为背包的重量C(C<10000)和物品个数N(N<1000)。接下来的N行分别为物品的重量cost(1<=cost<=100)和价值val(1<=val<=3000000)。(注意:结果可能超过int范围)

输出

对每组测试数据,输出其对应的所装物品的最大价值。

样例输入

1
2
3
4
5
6
7
1
10 5
2 6
2 3
6 5
5 4
4 6

样例输出

1
15

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
#include <iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

int w[1002] = { 0 };
long long v[1002] = { 0 };
long long m[1002][10002] = { 0 };

void Knapsack(int c, int n) {
int jMax = min(w[n] - 1, c);
for (int j = 0; j <= jMax; j++) {
m[n][j] = 0;
}
for (int j = w[n]; j <= c; j++) {
m[n][j] = v[n];
}
for (int i = n - 1; i >= 1; i--) {
jMax = min(w[i] - 1, c);
for (int j = 0; j <= jMax; j++) {
m[i][j] = m[i + 1][j];
}
for (int j = w[i]; j <= c; j++) {
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
}
}
}
int main() {
int T;
cin >> T;
while (T--) {
int c, n;
cin >> c >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
Knapsack(c, n);
cout << m[1][c] << endl;
}
return 0;
}

最大子段和

题目描述

给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj(子段可为空集)的最大值。

输入

包含多组测试数据。第一行为一个整数T(1<=T<=20),代表测试数据个数。

每组测试数据第一行为一个整数n,代表有n个整数(1<=n<=10000)。

接下来一行有n个数x(-1000<=x<=1000)。

输出

输出其对应的最大子段和。

子段可为空集,答案为0

样例输入

1
2
3
1
6
2 -11 4 13 -1 2

样例输出

1
18

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
#include <iostream>
#include<algorithm>
using namespace std;
int cmp(int a, int b) {
return b < a;
}

int a[10002] = { 0 };
int b[10002] = { 0 };

int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
b[1] = a[1];
for (int i = 1; i <= n; i++) {
if (b[i - 1] > 0) { b[i] = b[i - 1] + a[i]; }
else b[i] = a[i];
}
sort(b + 1, b + n + 1, cmp);
cout << b[1] << endl;
}
return 0;
}

汽水瓶

题目描述

有这样一道智力题:“某商店规定:三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶,她最多可以换多少瓶汽水喝?”答案是5瓶,方法如下:先用9个空瓶子换3瓶汽水,喝掉3瓶满的,喝完以后4个空瓶子,用3个再换一瓶,喝掉这瓶满的,这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水,喝掉这瓶满的,喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶,最多可以换多少瓶汽水喝?

输入

输入文件最多包含10组测试数据,每个数据占一行,仅包含一个正整数n(1≤n≤100),表示小张手上的空汽水瓶数。n=0表示输入结束,你的程序不应当处理这一行。

输出

对于每组测试数据,输出一行,表示最多可以喝的汽水瓶数。如果一瓶也喝不到,输出 0

样例输入

1
2
3
4
3
10
81
0

样例输出

1
2
3
1
5
40

AC代码

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
cout << n / 2 << endl;
}
return 0;
}
-------------end ♥-------------