演算法hw3_鐵條

 avatar
user_3763047219
c_cpp
2 years ago
884 B
3
Indexable
Never
int main()
{
	int k = 0;
	int p[100];
	scanf("%d", &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d", &p[i]);
	}
	int r[100] = { 0 }, s[100] = {0};
	for (int i = 1; i <= k; i++) {
		int q = -1;
		for (int j = 1; j <= i; j++) {
			if (q >= p[j] + r[i - j]) {
				q = q;
			}
			else {
				q = p[j] + r[i - j];
				s[i] = j;
			}
			r[i] = q;
		}
	}
	int s_total = 0;
	int s_index = k;
	int s_num[100] ;
	int index = 1;
	while (s_index != -1) {
		if (s[s_index] == s_index) {
			s_total = s_total + 1;
			s_num[index] = s[s_index];
			s_index = -1;
			index = index + 1;
		}
		else {
			s_total = s_total + 1;
			s_num[index] = s[s_index];
			s_index = s_index-s[s_index];
			index = index + 1;
		}
	}
	printf("%d\n%d\n", r[k], s_total);
	printf("%d=%d", k, s_num[1]);
	for (int i = 2; i <= s_total; i++) {
		printf("+%d", s_num[i]);
	}
	
}