PKU 2609 Ferry Loading

• 動的計画法
• 縦に車の数、横に2レーンのうち片方の車の総重量をとる
• DPが終わったらバックトラックして答えを求める

static char dp[256][16 * 1024];
int main() {
	int length;
	cin >> length;
	length *= 100;

	vector<int> cars;

	dp[0][0] = -1;

	int bestCarIndex = -1;
	int bestLength = -1;
	int sum = 0;

	for (int carIndex = 0; carIndex + 1 < 256; ++carIndex) {
		int car;
		cin >> car;
		sum += car;
		cars.push_back(car);

		if (car == 0) {
			break;
		}

		for (int l = 0; l <= length; ++l) {
			if (dp[carIndex][l] == 0) {
				continue;
			}

			if (l + car <= length) {
				dp[carIndex + 1][l + car] = 1;
				bestCarIndex = carIndex + 1;
				bestLength = l + car;
			}

			if (sum - l <= length) {
				dp[carIndex + 1][l] = 2;
				bestCarIndex = carIndex + 1;
				bestLength = l;
			}
		}
	}

	vector<string> answers;
	int currentLength = bestLength;
	for (int carIndex = bestCarIndex; carIndex > 0; --carIndex) {
		if (dp[carIndex][currentLength] == 1) {
			answers.push_back("starboard");
			currentLength -= cars[carIndex - 1];
		} else {
			answers.push_back("port");
		}
	}

	reverse(answers.begin(), answers.end());

	cout << answers.size() << endl;
	for (vector<string>::iterator it = answers.begin(), itEnd = answers.end(); it != itEnd; ++it) {
		cout << *it << endl;
	}
}