PAT-Advanced Array

1007 Maximum Subsequence Sum (25分)

解法一：线性扫描

太经典了就不说了

#include<iostream>
#include<vector>

int num, sum, max;
int start, end, index;
std::vector<int> array;

void parseInput() {
	std::cin >> num;
	array = std::vector<int>(num);
	for (int i = 0; i < num; i++) std::cin >> array[i];
}

void maxSubSequence() {
	sum = 0, max = array[0];
	start = 0, end = 0, index = array[0];
	for (int i = 0; i < num; i++) {
		sum += array[i];
		if (sum < 0) {
			sum = 0;
			index = i+1;
		}
		else if (sum > max) {
			max = sum;
			end = i;
			start = index;
		}
	}
}

int main() {
	parseInput();
	maxSubSequence();
	if (max < 0) 
		std::cout << 0 << " " << array[0] << " " << array[num - 1];
	else 
		std::cout << max << " " << array[start] << " " << array[end];
}

解法二：分治法

同样经典，但是麻烦一点，实战没必要这样做

1009 Product of Polynomials (25分)

解法一

开三个大数组+两重循环 憨憨式解法，但是有用

#include<iostream>

int num, expo, cnt = 0;
float coef;
float p1[1001] = { 0 }, p2[1001] = { 0 }, p3[2001] = { 0 };

void parseInput() {
	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> expo >> coef;
		p1[expo] = coef;
	}

	std::cin >> num;
	for (int i = 0; i < num; i++) {
		std::cin >> expo >> coef;
		p2[expo] = coef;
	}

}

void genProduct() {
	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			if (!p1[i] || !p2[j]) continue;
			expo = i + j;
			coef = p1[i] * p2[j];
			p3[expo] += coef;
		}
	}
	for (int i = 0; i < 2001; i++)
		if (p3[i] != 0) cnt++;
}

int main() {
	parseInput();
	genProduct();
	std::cout << cnt;
	for (int i = 2000; i > -1; i--)
		if (p3[i]) printf(" %d %.1f", i, p3[i]);
}