10003 나무 막대기 절단 문제

원제는 UVa10003 참조
본문은 주로 다음과 같은 내용을 포함한다.
1. 수학 모형의 구축
2. 위조 코드의 유도
3. 프로그램 구현
4. 요약
키워드:동적 계획 집합
1. 수학 모형의 구축
많은 사람들이 이 문제를 풀지 못하는데 근본적으로 문제의 뜻을 이해하지 못했다.우리 이제 처음부터 분석해 봅시다.
알려진 바와 같이 나무 막대기의 길이는 L이고 절단 포인트는 n이며 각 절단점의 위치도 고정되어 있다.매번 절단하는 비용은 절단된 나무 막대기의 길이와 같다.
요구 사항: 최소 비용
이 문제의 관건은 매번 절단하는 비용이 절단된 나무 막대기의 길이와 같다는 것을 이해하는 것이다
어떻게 이 말을 자르는 동작과 연결합니까?
현재 정의(i, j)는 i번째 절단점과 j번째 절단점에서 발생하는 나무 막대기를 나타낸다.
지금 이 나무 막대기를 절단하는데 절단점이 k번째 절단점이라고 가정하면 매우 명백하다
그러면 막대기(i,j)는 두 개의 막대기(i,k)(k,j)가 되고, 이번 절단에 드는 비용은 c[j]-c[i](주:c[i]로 왼쪽 절단점의 거리를 표시한다)
d[i][j]를 나무 막대기(i, j)를 절단하는 데 필요한 최소 비용으로 정의하면:
             d[i][j] = min{d[i][k]+d[k][j]+c[j]-c[i]}   k:i+1->j-1
왼쪽 끝을 각각 0번째와 n+1번째 절단점으로 보고 c[0]=0, c[n+1]=L
2. 위조 코드의 추측:
질문: 최초의 상태는 무엇입니까?
답: 최초의 상태는 더 이상 절단할 수 없는 나무 막대기였다.왜 더 이상 절단할 수 없는 나무 막대기인가?나무 막대기(i, j) 사이에 더 이상 절단점이 없고,
구체적으로 d[0][1]d[1][2]d[2][3]d[3][4]...d[n][n+1], 그것들은 더 이상 절단할 수 없기 때문에 그것들의 초기값은 모두 0이다.
                
그 다음에 계산해야 할 것은 한 칼에 잘릴 수 있는 나무 막대기다.
구체적으로 d[0][2]d[1][3]...... d[n-1][n+1]
다음은 d[0][3]d[1][4]... d[n-2][n+1]
                
마지막 결과는 d[0][n+1]
따라서 i, j에 포함된 절단점수p는 1층 순환p:1->n
i는 2층 순환, i:0->n
k는 3층 순환 k:i+1->j-1
위조 코드는 다음과 같습니다.
           memset(d,0,sizeof(d));
           for p:1->n
                do  for i:0->n
                       j = i+p;
                      if j>n+1   break
                     for  k:i+1->j-1
                            d[i][j] = min{d[i][k]+d[k][j]+c[j]-c[i]} 
3. 구체적인 코드 구현

#include
using namespace std;


int n;
int L;
int f[50][50];
int c[50];
const int INF = 99999;

int main(){
	cin >> L;
	cin >> n;

	c[0] = 0;
	c[n + 1] = L;
	for (int i = 1; i > c[i];

	memset(f, 0, sizeof(f));
	for (int p = 1; p <= n + 1; p++){
		for (int i = 0; i <= n + 1; i++){
			int j = i + p;
			if (j > n + 1) break;

			int min = INF;
			for (int k = i + 1; k < j; k++){
				int t = f[i][k] + f[k][j] + c[j] - c[i];
				if (t < min) min = t;
			}
			if (min != INF)f[i][j] = min;
		}//for i
	}//for p
	

	cout << f[0][n + 1];
	
}

4. 요약
대다수의 할 줄 모르는 것은 문제를 전혀 읽지 못했기 때문이다.
대부분의 논리적 버그는 문제를 읽지 못한 데 있다.
독제, 독제, 독제.이해해, 이해해.
이 문제에서 상태에 따라 방정식을 옮기는 추이 프로그램을 어떻게 쓰는지 총결하였다.
상태 이동 방정식을 쓰는 것과 구체적인 프로그램을 쓰는 것은 두 번의 일이다. 상태 이동 방정식을 쓰는 것이 구체적인 프로그램의 실현 사이에 위조 코드를 사이에 두고 있는 과정이다.이 과정은 논리가 복잡한 문제에 매우 중요하다!
그러니까 문제읽기+위조코드 쓰기!