uva 10003 - Cutting Sticks(dp)
제목:
나무의 n (n < 50) 위 치 를 잘라 야 합 니 다.자 르 는 데 드 는 나무 길이 의 길이.이 n 곳 을 자 르 는 데 드 는 최소 비용 을 물 어보 세 요.
생각:
역 발상 할 수 있다.나 무 를 한 토막 으로 합성 하 다.합병 비용 은 합병 후의 길이 입 니 다.그래서 곧 O (n ^ 3) 의 알고리즘 을 얻 을 수 있 습 니 다.n 이 비교적 작 아서 충분히 쓸 수 있다.dp [i] [j] 는 합병 완료 [i, j] 의 최소 비용 을 표시 합 니 다.dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])。k€(i,j)。
자세 한 코드 참조:
#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
//typedef __int64 ll;
int dp[100][100],pos[100];
int main()
{
int l,n,i,len,k;
while(scanf("%d",&l),l)
{
scanf("%d",&n);
memset(dp,0x3f,sizeof dp);
pos[0]=0;
for(i=1;i<=n;i++)
scanf("%d",&pos[i]);
n++;
pos[n]=l;// n
for(i=1;i<=n;i++)
dp[i][i]=0;
for(len=2;len<=n;len++)//
for(i=1;i<=n+1-len;i++)
{
for(k=i;k<i+len-1;k++)
dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]);
dp[i][i+len-1]+=pos[i+len-1]-pos[i-1];
}
printf("The minimum cutting is %d.
",dp[1][n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
