uva10003Cutting Sticks(DP)
1624 단어 dp
제목 대의: 나무 막대기의 길이 l을 주고 n개의 수 c1~cn을 주면 나무 막대기의 한쪽 끝 길이ci에서 한 칼씩 자르는 것을 의미한다. 한 칼의 대가는 현재 자른 나무 막대기의 길이다.최소의 총대가를 구하다.
제목 분석: 자세히 보면 이것은 사실 돌의 합병 문제이다. 단지 하나의 자세를 바꿨을 뿐이다. 하나는 합병이고 하나는 자르고 본질은 똑같다.
나는 이 문제를 석자 합병 문제 dp로 바꾸었다.
나무 막대기로 n칼을 자르면 n+1단이 생기는데 그의 역과정은 n+1더미의 돌을 한 무더기로 합치는 것이다.
dp[i][j]는 i단부터 시작된 j단 나무 막대기의 총 대가를 나타낸다.그러면 i에서 j까지의 단락은 i에서 k까지의 +k에서 j까지의 단락이기 때문에 i에서 j까지의 직접적인 k를 열거할 수 있고 방정식이 있다.
dp[i][j] = min(dp[i][k] + dp[i + k][j - k] + sum(i,j),dp[i][j]);(1<= k < j);
dp[i][1] = 세그먼트의 원래 길이입니다.
각 단락의 원시 길이는 총 대가를 계산하지 않기 때문에 마지막에 원시 길이를 줄여야 한다. 원시 길이의 합은 바로 나무 막대기의 길이이다.
자세한 내용은 코드 참조:
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55;
int lcm[N];
int dp[N][N];
int n,l;
int main()
{
int i,j,k;
while(scanf("%d",&l),l)
{
scanf("%d",&n);
lcm[0] = 0;lcm[n + 1] = l;
for(i = 1;i <= n; i ++)
scanf("%d",lcm + i);
sort(lcm + 1,lcm + 1 + n);
memset(dp,1,sizeof(dp));
for(i = 1;i <= n + 1;i ++)
dp[i][1] = lcm[i] - lcm[i - 1];
for(i = 2;i <= n + 1;i ++)//l
{
for(j = 1;i + j <= n + 2;j ++)
{
for(k = 1;k <= i - 1;k ++)
dp[j][i] = min(dp[j][i],dp[j][k] + dp[j + k][i - k] + lcm[i + j - 1] - lcm[j - 1]);
}
}
printf("The minimum cutting is %d.
",dp[1][n + 1] - l);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
