Rod_Cuttinf 鐵條

#include <iostream>

int main()
{
	int k = 0;
	int p[101] = {};
	scanf("%d", &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d", &p[i]);
	}
	int s[101] = {};//紀錄最好的一刀
	int r[101] = {};//紀錄最終需要多少錢
	for (int i = 1; i <= k; i++) {//所有長度的情況
		int q = 0;
		for (int j = 1; j <= i; j++) {//長度為i的鐵條切法
			if (q < r[i - j] + p[j]) {
				q = r[i - j] + p[j];
				s[i] = j;//放入最好的切法 !
			}
		}
		r[i] = q;
	}
	int total = 0;
	int k2 = k;
	int ans[101] = {};
	while (k2>0) {
		if (s[k2] == k2) {
			total = total + 1;
			ans[total] = s[k2];
			break;
		}
		else {
			total = total + 1;
			ans[total] = s[k2];
			k2 = k2 - s[k2];
		}
	}
	printf("%d\n", r[k]);
	printf("%d\n", total);
	printf("%d=%d", k ,ans[1]);
	for (int i = 2; i <= total; i++) {
		printf("+%d", ans[i]);
	}

}