[UVA 10003]Cutting Sticks[DP]
제목 분석: 나무 막대기를 제시한 다음에 그것을 절단해야 한다. 매번 절단 비용은 절단된 나무 막대기의 길이이다.예를 들어 길이가 10미터이고 4미터에서 절단하는데 절단된 나무 막대기의 길이가 10미터이기 때문에 비용은 10미터이다.질문: 승차순은 절단해야 할 모든 점을 제시하는데 가장 적은 절단 비용은 얼마입니까?
문제풀이 사고방식: 상태: dp[i][j]는 절단구간[i,j]에 필요한 최소 비용을 나타낸다.이전: dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+j-i+1)(k는 i, j가 포함하는 절단이 필요한 점);경계: 구간에 절단이 필요한 점이 존재하지 않을 때 비용은 0이다.i>j일 때 이런 절단이 존재하지 않고 0으로 돌아갑니다(이 절단은 결과에 영향을 주지 않는다는 뜻).
개인적인 느낌: DP는 정말 신기한 것 같아요. 우선 상태, 상태를 알아야 해요. 상태를 알아야 해요. 어떻게 옮기는지 알아야 해요. 옮기는 것도 알아야 해요. XD를 어떻게 인코딩하는지 알아야 해요.하지만 정확한 컨디션 구축은 모든 것의 초석이야~ 이 문제는 자서상의 컨디션을 보면 알 수 있어...그리고 스스로 비비는 버전을 썼어요. 시간 1.8s예요.인터넷에 있는 코드가 XD 버전을 더 많이 낼 수 있도록 문제풀이도 씁니다
구체적인 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 61;
int n,l;
bool cut[1111]; // ： ？ ？
int dp[1111][1111];
bool have(int l, int r) //
{
for (int i = l; i <= r; ++i)
if (cut[i]) return 1;
return 0;
}
int dfs(int l, int r)
{
int &ret = dp[l][r];
if(!have(l,r)) return ret = 0; //
if(l > r ) return ret = 0; //
if(ret < INF) return ret;
for (int i = 1; i <= r; ++i)
{
if (cut[i])
{
cut[i] = 0;
ret = min(ret, dfs(l, i) + dfs(i + 1, r) + r - l + 1);
cut[i] = 1;
}
}
return ret;
}
int main()
{
while (cin >> l && l)
{
int x;
cin >> n;
memset(cut, 0, sizeof cut);
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < n; ++i) cin >> x, cut[x] = 1;
int ans = INF;
cout << "The minimum cutting is " << dfs(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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
