[UVA10003] 나무 막대기 dp
904 단어 UVa동적 기획 - 단순 dp
자서야, 자세하게 얘기했어.
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
int dp[501][501],a[1005];
int n,m,len;
int read()
{
char ch=getchar();int ret=0,f=1;
while(ch'9') {if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return f*ret;
}
int main()
{
while(1)
{
len=read();if (!len) break;
n=read();
for (int i=1;i<=n;i++) a[i]=read();
a[0]=0;a[n+1]=len;
for (int l=1;l<=n+1;l++)
{
for (int i=0;i+l<=n+1;i++)
{
int j=i+l,temp=inf;
for (int k=i+1;k<=j-1;k++)
temp=min(temp,dp[i][k]+dp[k][j]+a[j]-a[i]);
if (temp!=inf) dp[i][j]=temp;
}
}
printf("The minimum cutting is %d.
",dp[0][n+1]);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVa 548 트리제목: 중순과 후순 서열을 제시하고 뿌리에서 잎사귀 결점까지의 경로와 값이 가장 작은 잎사귀 결점을 구한다.값과 같으면 잎사귀 결점 값이 비교적 작은 것을 선택하십시오. 사고방식: 중순과 후순 서열로 돌아가며 두 갈...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
