uva 10003 Cutting Sticks 막대 dp

1305 단어
이 문제는 약간 유사한 행렬 연승이 있는데, 바로 구간의 문제이다.dp[i][j]를 설정하면 i에서 j까지의 최소 비용을 나타낸다. 그러면 dp[i][j]=min{dp[i]
[k]+dp[k][j]+a[j]-[i]}(i이 문제는 0과 나무 줄기의 길이를 a로 늘렸다.
수조 안에는 모두 n+2개의 점이 있는데, 두 개의 인접한 점은 절단하지 않고 1로 초기화된다.
코드:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	int s,n;
	int dp[55][55];
	int a[55];
	int i,j,r,k,t,m;
	while(cin >> s,s)
	{
		cin >> n;
		a[1] = 0;
		a[n+2] = s;
		for(i=2; i<=n+1; i++)
			cin >> a[i];
		m = n+2;
		for(i=1; i<m; i++)
			dp[i][i+1] = 0;
		for(r=2; r<=m-1; r++)//r       ,   2,   m-1 
		{
			for(i=1; i<=m-r; i++)//i       ,   1,     r   
			{
				j=i+r;//j        
				dp[i][j] = dp[i+1][j] +dp[i][i+1] + a[j]-a[i];
				for(k=i+2; k<j; k++)
				{
					t = dp[i][k] + dp[k][j] + a[j] - a[i];
					if(t < dp[i][j])
						dp[i][j] = t;
				}
			}
		}
		cout << "The minimum cutting is "<< dp[1][m] << '.'<< endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기